algorithm - How to revert change of ArrayList after using List.set() JAVA -

i have arraylist of items (each item weight , profit):

arraylist itemlist: [{weight: 3, profit: 10}, {weight: 15, profit: 50}, {weight: 7, profit: 25}, {weight: 6, profit: 15}, {weight: 4, profit: 10}]

then have random bitstrings representing items taken given maximum weight taken 20 (capacity = 20).

let's initial random bits obtain [1,1,0,0,0] means item 1 , item 2 taken give:

totalweight = 3 + 15 = 18 [<= capacity]

then have random bit flipped (if bit 1 -> 0, , if bit selected flip 0 -> 1). let's order flip bits [3,2,1,4,0].

so firstly, bit @ index 3 flipped , count total weight this:

[1,1,0,0,0] --> [1,1,0,1,0]

hence, new bitstring after bit[3] flip: [1,1,0,1,0].

then count total weight again:

total weight of new bitstring = 3 + 15 + 6 = 24 [> capacity]

so total exceeds capacity , want new bitstring assign previous bitstring before flip:

[1,1,0,1,0] --> return previous state: [1,1,0,0,0].

after return state: [1,1,0,0,0] next bit flip order [3,2,1,4,0] have flip bit @ index 2 according order left right. becomes:

from [1,1,0,0,0] --> flip bit[2]:

[1,1,0,0,0] --> [1,1,1,0,0]

then same calculate weight etc.

if total still exceeds return previous state if not exceeds add new solution new arraylist.

i have done codings on problems previous state , @ adding accepted bit strings arraylist improve. stores latest updated solution , other accepted solutions being replaced shown in output obtain.

this codes: '

  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);      (int = 0; < fliporder.size(); i++){         int totalweight = 0, totalprofit = 0;          pointer = fliporder.get(i);         toflip = solution.get(pointer);          (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 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 previous state}: " + currentsolution);              if (toflip == 1){                 solution.set(pointer, 0);             }             else if (toflip == 0){                 solution.set(pointer, 1);             }             system.out.println("solution after flip 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;      (int = 0; < 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 = 0;         string str;         while ( (str = in.readline() )!= null ) {             string[] item = str.split( "," );             //system.out.print("weight #" + + " : " + integer.parseint(item[0]));             //system.out.print("profit #" + + " : " + 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 file 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 random boolean values     boolean[] booleans = new boolean[length];     (int = 0; < booleans.length; i++) {       booleans[i] = r.nextboolean();     }      (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();      (int = 0; < length; i++){         order.add(i);     }      collections.shuffle(order);      return order;    }   } 

'

my textfile consists following (weight, profit):

3,10

15,50

7,25

6,15

4,10

my output obtained (the initial bit strings , random order flip bit randomly generated):

list of items: [{weight: 3, profit: 10}, {weight: 15, profit: 50}, {weight: 7, profit: 25}, {weight: 6, profit: 15}, {weight: 4, profit: 10}]

initial solution: [1, 0, 0, 1, 0]

current solution: [1, 0, 0, 1, 0]

random order: [2, 4, 0, 1, 3]

updated solution: [1, 0, 0, 1, 0]

total weight solution 1 : 9 | total profit solution 1 : 25

----------not exceed-----------

currentsolution before flip: [1, 0, 0, 1, 0]

improve: [[1, 0, 0, 1, 0]]

solution after flip random order [2] : [1, 0, 1, 1, 0]

---

updated solution: [1, 0, 1, 1, 0]

total weight solution 2 : 16 | total profit solution 2 : 50

----------not exceed-----------

currentsolution before flip: [1, 0, 1, 1, 0]

improve: [[1, 0, 1, 1, 0], [1, 0, 1, 1, 0]] it doesn't store previous accepted solution replace new one

solution after flip random order [4] : [1, 0, 1, 1, 1]

---

updated solution: [1, 0, 1, 1, 1]

total weight solution 3 : 20 | total profit solution 3 : 60

----------not exceed-----------

currentsolution before flip: [1, 0, 1, 1, 1]

improve: [[1, 0, 1, 1, 1], [1, 0, 1, 1, 1], [1, 0, 1, 1, 1]]

solution after flip random order [0] : [0, 0, 1, 1, 1]

---

updated solution: [0, 0, 1, 1, 1]

total weight solution 4 : 17 | total profit solution 4 : 50

----------not exceed-----------

currentsolution before flip: [0, 0, 1, 1, 1]

improve: [[0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]

solution after flip random order [1] : [0, 1, 1, 1, 1]

---

updated solution: [0, 1, 1, 1, 1]

total weight solution 5 : 32 | total profit solution 5 : 100

----------exceed!!!!------------

currentsolution before flip {return previous state}: [0, 1, 1, 1, 1] ==> should return [0,0,1,1,1] capacity not exceeded

solution after flip random order [3] : [0, 1, 1, 0, 1] ==> should flipped [0,0,1,1,1] , bcomes -> [0,0,1,0,1]

---

and lastly, once has becomes [0,0,1,0,1] should display total weight again , display it's not displaying.

i'm not sure mistakes. please help. thank you.

i have edited code make shorter. still haven't managed previous bitstrings if weight exceeds.

this updated codes: '

  public class bitstring {     public static void main (string[] args){     int n = 3, capacity = 11, pointer, toflip;      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>>();      itemlist.add(new item(4,5));     itemlist.add(new item(10,12));     itemlist.add(new item(5,8));      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);      (int = 0; < fliporder.size(); i++){         int totalweight = 0, totalprofit = 0;          pointer = fliporder.get(i);         toflip = solution.get(pointer);          system.out.println();          (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("total weight solution " + solution + " : " + totalweight + " | total profit solution " + solution + " : " + totalprofit);          if (totalweight <= capacity){             system.out.println(totalweight + " not exceed capacity solution: " + solution);             currentsolution = solution;             improve.add(currentsolution);             system.out.println("updated current solution: " + currentsolution);             system.out.println("updated improved: " + improve);              //do flipping bits             if (toflip == 1)                 solution.set(pointer, 0);             else                 solution.set(pointer, 1);              system.out.println("new solution after flip: " + solution);         }         else{             system.out.println(totalweight + " exceeds capacity solution: " + solution);             solution = currentsolution;             system.out.println("solution reverted: " + solution);              //do flipping bits             if (toflip == 1)                 solution.set(pointer, 0);             else                 solution.set(pointer, 1);              system.out.println("new solution after flip: " + solution);         }      }  }  //generate initial solution(bits) randomly public static arraylist<integer> initialsolution(int length){     random r = new random();     arraylist<integer> solution = new arraylist<integer>(length);      // generate random boolean values     boolean[] booleans = new boolean[length];     (int = 0; < booleans.length; i++) {       booleans[i] = r.nextboolean();     }      (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();      (int = 0; < length; i++){         order.add(i);     }      collections.shuffle(order);      return order;    }   } 

'

and output is:

list of items: [{weight: 4, profit: 5}, {weight: 10, profit: 12}, {weight: 5, profit: 8}]

initial solution: [0, 1, 0]

current solution: [0, 1, 0]

random order: [2, 0, 1]

total weight solution [0, 1, 0] : 10 | total profit solution [0, 1, 0] : 12

10 not exceed capacity solution: [0, 1, 0]

updated current solution: [0, 1, 0]

updated improved: [[0, 1, 0]]

new solution after flip: [0, 1, 1]

total weight solution [0, 1, 1] : 15 | total profit solution [0, 1, 1] : 20

15 exceeds capacity solution: [0, 1, 1]

solution reverted: [0, 1, 1]

new solution after flip: [1, 1, 1]

total weight solution [1, 1, 1] : 19 | total profit solution [1, 1, 1] : 25

19 exceeds capacity solution: [1, 1, 1]

solution reverted: [1, 1, 1]

new solution after flip: [1, 0, 1]