使用列表后如何还原ArrayList的更改的算法。set（）JAVA
我有一个物品列表（每个物品都有重量和利润）：
ArrayList项目列表： [{重量：3，利润：10}，{重量：15，利润：50}，{重量：7，利润：25}，{重量：6，利润：15}，{重量：4，利润：10}]
然后我有一个随机的位字符串，表示在最大权重为20（容量=20）的情况下，要获取的项目
假设获得的初始随机位为[1,1,0,0,0]，这意味着取第1项和第2项，它们给出：
总重量=3+15=18[<；=容量]
然后我有一个要翻转的随机位（如果位是1->；0，如果选择翻转的位是0->；1）。假设翻转位的顺序是[3,2,1,4,0]
因此，首先，索引3处的位将翻转，并按如下方式计算总权重：
[1,1,0，0，0]-->；[1,1,0，1，0]
因此，位[3]之后的新位字符串翻转：[1,1,0,1,0]
然后再次计算总重量：
新位字符串的总重量=3+15+6=24[>；容量]
因此，总容量超过容量，我希望新的位字符串在翻转之前分配回前一个位字符串：
[1,1,0，1，0]-->；返回到以前的状态：[1,1,0，0，0]
返回到状态：[1,1,0,0,0]后，下一位将从刚才的顺序翻转[3,2,1,4,0]，但现在我必须按照从左到右的顺序翻转索引2处的位。这就变成了：
从[1,1,0,0,0]——>；翻转位[2]：
[1,1，0，0,0]-->；[1,1，1，0,0]
然后做同样的计算重量等
如果总数仍然超过，它将返回到以前的状态，但如果不超过，它将向新的ArrayList添加新的解决方案
我已经对它进行了一些编码，但我的问题是回到以前的状态，并将接受的位字符串添加到ArrayList中。它只存储最新更新的解决方案，其他已接受的解决方案将被替换，如我获得的输出所示
这是我的密码： “是的
public class KnapsackHC {
public static void main (String[] args){
int n = 5, capacity = 20, pointer, toFlip;
//Item items = new Item();
ArrayList<Item> itemList = new ArrayList<Item>();
ArrayList<Integer> solution = new ArrayList<Integer>();
ArrayList<Integer> currentSolution = new ArrayList<Integer>();
ArrayList<Integer> flipOrder = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> improve = new ArrayList<ArrayList<Integer>>();
//ArrayList<Integer> temp = new ArrayList<Integer>();
itemList = getProblem();
solution = initialSolution(n);
currentSolution = solution;
flipOrder = randomFlipOrder(n);
System.out.println("List of Items: " + itemList);
System.out.println("Initial solution: " + solution);
System.out.println("Current solution: " + currentSolution);
System.out.println("Random order: " + flipOrder);
for (int i = 0; i < flipOrder.size(); i++){
int totalWeight = 0, totalProfit = 0;
pointer = flipOrder.get(i);
toFlip = solution.get(pointer);
for (int j = 0; j < solution.size(); j++){
if (solution.get(j) == 1){
totalWeight += itemList.get(j).getWeight();
totalProfit += itemList.get(j).getProfit();
}
}
System.out.println();
System.out.println("Updated Solution: " + currentSolution);
System.out.println("Total Weight Solution " + (i+1) + " : " + totalWeight + " | Total Profit Solution " + (i+1) + " : " + totalProfit);
if (totalWeight <= capacity){
System.out.println("----------NOT EXCEED-----------");
currentSolution = solution;
System.out.println("currentSolution BEFORE FLIP: " + currentSolution);
improve.add(currentSolution);
System.out.println("Improve: " + improve);
if (toFlip == 1){
solution.set(pointer, 0);
}
else if (toFlip == 0){
solution.set(pointer, 1);
}
System.out.println("solution AFTER FLIP from Random Order [" + flipOrder.get(i) + "] : " + solution);
currentSolution = solution;
//solution = new ArrayList<Integer>();
System.out.println("--------------------------------");
}
else{
System.out.println("----------EXCEED!!!!------------");
//currentSolution = solution;
System.out.println("currentSolution BEFORE FLIP {return back to previous state}: " + currentSolution);
if (toFlip == 1){
solution.set(pointer, 0);
}
else if (toFlip == 0){
solution.set(pointer, 1);
}
System.out.println("solution AFTER FLIP from Random Order [" + flipOrder.get(i) + "] : " + solution);
System.out.println("--------------------------------");
}
}
}
/*
public static ArrayList<Integer> calcFitness(ArrayList<Integer> currentSolution, ArrayList<Integer> solution, ArrayList<Item> itemList, int capacity){
System.out.println("\nAfter Flip: " + solution);
System.out.println("Current Solution: " + currentSolution);
int totalWeight = 0;
int totalProfit = 0;
for (int i = 0; i < solution.size(); i++){
if (solution.get(i) == 1){
totalWeight += itemList.get(i).getWeight();
totalProfit += itemList.get(i).getProfit();
}
}
System.out.println("Total Weight: " + totalWeight + " || Total Profit: " + totalProfit);
if (totalWeight <= capacity){
currentSolution = solution;
System.out.println("Solution change: " + currentSolution);
System.out.println();
return solution;
}
else{
System.out.println("Solution NO change: " + currentSolution);
System.out.println();
return currentSolution;
}
}*/
public static ArrayList<Item> getProblem(){
ArrayList<Item> itemsArr = new ArrayList<Item>();
try {
BufferedReader in = new BufferedReader( new FileReader("knapsack_problem_5.txt" ) );
int i = 0;
String str;
while ( (str = in.readLine() )!= null ) {
String[] item = str.split( "," );
//System.out.print("Weight #" + i + " : " + Integer.parseInt(item[0]));
//System.out.print("Profit #" + i + " : " + Integer.parseInt(item[1]));
int weight = Integer.parseInt(item[0]);
int profit = Integer.parseInt(item[1]);
itemsArr.add(i,new Item(weight,profit));
i++;
}
in.close();
} catch ( IOException ex ) {
System.err.println( "Error: Can't open the file for reading." );
}
return itemsArr;
}
//generate initial solution(bits) randomly
public static ArrayList<Integer> initialSolution(int length){
Random r = new Random();
ArrayList<Integer> solution = new ArrayList<Integer>(length);
// generate some random boolean values
boolean[] booleans = new boolean[length];
for (int i = 0; i < booleans.length; i++) {
booleans[i] = r.nextBoolean();
}
for (boolean b : booleans) {
if (b == true){
solution.add(1);
}
else{
solution.add(0);
}
}
return solution;
}
public static ArrayList<Integer> randomFlipOrder(int length){
ArrayList<Integer> order = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0; i < length; i++){
order.add(i);
}
Collections.shuffle(order);
return order;
}
}
“是的
我的文本文件包括以下内容（重量、利润）：
3,10
15,50
7,25
6,15
4,10
获得我的输出（将随机生成初始位字符串和翻转位的随机顺序）：
项目清单：[重量：3，利润：10}，{重量：15，利润：50}，{重量：7，利润：25}，{重量：6，利润：15}，{重量：4，利润：10}]
初始解：[1,0,0,1,0]
当前解决方案：[1,0,0,1,0]
随机顺序：[2,4,0,1,3]
更新的解决方案：[1,0,0,1,0]
总重量方案1:9 |总利润方案1:25
-------不超过-----------
翻转前的currentSolution:[1,0,0,1,0]
提高：[[1,0,0,1,0]]
从随机顺序[2]翻转后的解决方案：[1,0,1,1,0]
更新的解决方案：[1,0,1,1,0]
总重量方案2:16 |总利润方案2:50
-------不超过-----------
翻转前的currentSolution:[1,0,1,1,0]
改进：[[1,0,1,1,0]，[1,0,1,1,0]它不存储以前接受的解决方案，而是用新的解决方案替换它
从随机顺序翻转后的解决方案[4]：[1,0,1,1,1]
更新的解决方案：[1,0,1,1,1]
总重量方案3:20 |总利润方案3:60
-------不超过-----------
翻转前的当前解决方案：[1,0,1,1,1]
提高：[[1,0,1,1,1]，[1,0,1,1,1]，[1,0,1,1,1]]
从随机顺序[0]翻转后的解决方案：[0,0,1,1,1]
更新的解决方案：[0,0,1,1,1]
总重量方案4:17 |总利润方案4:50
-------不超过-----------
翻转前的当前解决方案：[0，0,1,1,1]
提高：[[0,0,1,1,1]，[0,0,1,1,1]，[0,0,1,1,1]，[0,0,1,1,1]]
从随机顺序[1]翻转后的解决方案：[0,1,1,1]
更新的解决方案：[0,1,1,1,1]
总重量方案5:32 |总利润方案5:100
-------超过------------
翻转前的currentSolution{return back to previous state}:[0,1,1,1,1]=>；这应该返回到[0,0,1,1,1]，其中容量没有超过
从随机顺序翻转后的解决方案[3]：[0,1,1,0,1]=>；这应该从[0,0,1,1,1]和bcomes翻转过来->；[0,0,1,0,1]
最后，当它变成[0,0,1,0,1]时，它应该再次显示总重量并显示，但它不显示
我不确定错误在哪里。请帮忙。谢谢
# 1 楼答案
我对代码进行了编辑，使其更短。如果权重超过，我仍然无法获得前面的位字符串
这是我的最新代码： “是的
“是的
我的输出是：
项目清单：[{重量：4，利润：5}，{重量：10，利润：12}，{重量：5，利润：8}]
初始解：[0,1,0]
当前解决方案：[0,1,0]
随机顺序：[2,0,1]
解决方案的总重量[0,1,0]：10 |解决方案的总利润[0,1,0]：12
10不超过解决方案的容量：[0,1,0]
更新的当前解决方案：[0,1,0]
更新改进：[[0,1,0]]
翻转后的新解决方案：[0,1,1]
解决方案[0,1,1]的总重量：15 |解决方案[0,1,1]的总利润：20
15超出解决方案的容量：[0,1,1]
已还原解决方案：[0,1,1]
翻转后的新解决方案：[1,1,1]
解决方案[1,1,1]的总重量：19 |解决方案[1,1,1]的总利润：25
19超出解决方案的容量：[1,1,1]
已还原解决方案：[1,1,1]
翻转后的新解决方案：[1,0,1]