用户交易算法

设计一个高效的算法,该算法将交易数n,大小si和费用f、依赖列表,1=1,n,以及索引集J드12-n作为输入,并返回所有交易(索引)的列表T(J드T),如果交易t:j∈要被包含在一个区块中,则必须包含这些交易(索引),从而使依赖规则得到尊重。例如,当」={4,7가,我们有T]={1,2,3,4,가。请注意,T必须包含」作为一个子集。

image.png

package com.demo;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Optional;

/**
 * Copyright:www.zhaoyang.wicp.vip
 * Author:王昭阳 -小明机器人
 * Date:2021/10/15
 * Description:代码版权声明
 */
public class TransactionNode {
    int n = 0;//交易数量
    int size;//交易尺寸
    int free;//交易费用
    String tj;
    List<TransactionNode> myList = new ArrayList<>();

    public TransactionNode(String tj, int size, int free) {
        this.size = size;
        this.free = free;
        this.tj = tj;
        getN(myList);
    }

    public void addTrans(TransactionNode transactionNode) {
        myList.add(transactionNode);
    }

    //获取交易的数量
    public int getN(List<TransactionNode> list) {
        if (list.size() == 0) n = 0;
        else {
            n += list.size();
            for (int i = 0; i < list.size(); i++) {
                n += getN(list.get(i).myList);
            }
        }
        if (n > 18) {
            System.out.println("区块过大");
        }
        return n;
    }

    @Override
    public String toString() {
        return

                ", tj='" + tj + '\'';


    }

    public void showTransList() {
        System.out.println(toString());
        for (int i = 0; i < myList.size(); i++) {
            myList.get(i).showTransList();
        }
    }

    public List<TransactionNode> showTransReturnList() {
        Optional<TransactionNode> demo = Optional.of(this);
        List<TransactionNode> list = new ArrayList<>();
        if (demo.isPresent()) {
            list.add(demo.get());
        }
        for (int i = 0; i < myList.size(); i++) { //遍历他的结点
            List<TransactionNode> list1 = myList.get(i).showTransReturnList();
            list.addAll(list1);
        }
        return list;
    }


}

package com.demo;

import java.util.*;

/**
 * Copyright:www.zhaoyang.wicp.vip
 * Author:王昭阳 -小明机器人
 * Date:2021/10/15
 * Description:代码版权声明
 */
public class TransactionNodeUtil {
    private List<TransactionNode> list_all = new ArrayList<>();

    public TransactionNodeUtil(List<TransactionNode> list_all) {
        this.list_all = list_all;
    }

    public List<TransactionNode> getIndexList() {
        List<TransactionNode> indexs = getList();
        List<TransactionNode> listWithoutDuplicates = withoutDuplicate(indexs);
        return listWithoutDuplicates;
    }


    public int totalFee() {
        int total = 0;
        for (int i = 0; i < getIndexList().size(); i++) {//总费用
            total += getList().get(i).free;
        }
        return total;
    }

    public int getAllSize() {
        int total = 0;
        List<TransactionNode> indexList = getIndexList(); //不去重复求尺寸
        for (int i = 0; i < indexList.size(); i++) {
            total += indexList.get(i).size;
        }
        return total;
    }
    public int getMaxProfit() {
        int total = 0;
        for (int i = 0; i < getIndexList().size(); i++) {//总费用
            total += getIndexList().get(i).free;
        }
        total = totalFee() - total;
        return total;

    }

    private List<TransactionNode> getList() {
        List<TransactionNode> indexList = this.list_all;
        //输入参数索引集合 返回索引
        List<TransactionNode> indexs = new ArrayList<>();
        Iterator<TransactionNode> iterator = indexList.iterator();
        while (iterator.hasNext()) {
            TransactionNode next = iterator.next();
            List<TransactionNode> list = next.showTransReturnList();
            indexs.addAll(list);
        }

        return indexs;
    }


    //没有重复
    private List<TransactionNode> withoutDuplicate(List<TransactionNode> indexs) {
        LinkedHashSet<TransactionNode> hashSet = new LinkedHashSet<>(indexs);//去重复
        ArrayList<TransactionNode> listWithoutDuplicates = new ArrayList<>(hashSet);
        return listWithoutDuplicates;
    }
}

```
package com.demo;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright:www.zhaoyang.wicp.vip
 * Author:王昭阳 -小明机器人
 * Date:2021/10/15
 * Description:代码版权声明
 */
public class Client {
    public static void main(String[] args) {
        setUp();

    }

    public static void setUp() {
        TransactionNode t10 = new TransactionNode("t10", 1, 2);
        TransactionNode t11 = new TransactionNode("t11", 2, 3);
        TransactionNode t12 = new TransactionNode("t12", 1, 4);

        TransactionNode t1 = new TransactionNode("t1", 1, 1);
        TransactionNode t2 = new TransactionNode("t2", 2, 1);
        TransactionNode t3 = new TransactionNode("t3", 1, 2);
        TransactionNode t4 = new TransactionNode("t4", 4, 3);
        TransactionNode t5 = new TransactionNode("t5", 3, 4);
        TransactionNode t6 = new TransactionNode("t6", 2, 2);
        TransactionNode t7 = new TransactionNode("t7", 3, 4);
        TransactionNode t8 = new TransactionNode("t8", 3, 2);
        TransactionNode t9 = new TransactionNode("t9", 3, 2);
        t10.addTrans(t6);
        t10.addTrans(t8);
        t11.addTrans(t7);
        t11.addTrans(t2);
        t12.addTrans(t8);
        t12.addTrans(t9);
        t6.addTrans(t3);
        t7.addTrans(t3);
        t8.addTrans(t3);
        t9.addTrans(t4);
        t9.addTrans(t5);
        t3.addTrans(t1);
        t4.addTrans(t1);
        t4.addTrans(t2);
        List<TransactionNode> j = new ArrayList<>();
        //{5,10,11} 索引集
        j.add(t5);
        j.add(t10);
        j.add(t11);
//        j.add(t12);
        TransactionNodeUtil transactionNodeUtil = new TransactionNodeUtil(j);

        //返回交易列表{5，10，6，8，11，7，2}
        List<TransactionNode> tj = transactionNodeUtil.getIndexList(); //打印交易列表
      System.out.println(tj);//打印交易列表


        System.out.println(transactionNodeUtil.getAllSize());
       System.out.println(transactionNodeUtil.totalFee() + "元");//打印总fee
//        2输出的交易（索引）集J∗，其总size和（最大）总利润（fee）

//        System.out.println(transactionNodeUtil.getMaxProfit());


        t5.showTransList();



    }
}

```