设计一个高效的算法,该算法将交易数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();
}
}
```
