package knapsack2;

/**
 * O(nW)
 */
public class Solver implements SolverInterface {
    private int[][] table;
    private Instance instance;

    @Override
    public Solution solve(Instance instance) {
        int W = instance.getWeightLimit();
        int n = instance.getSize();

        this.instance = instance;
        /* Initialize table with -1 */
        table = new int[n][W + 1];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= W; j++) {
                table[i][j] = -1;
            }
        }

        int bestValue = calculate(0, W);

        return backtrack(bestValue);
    }

    public int calculate(int item, int currentVolume) {
        if (item >= instance.getSize()) {
            return 0;
        }

        int itemWeight = instance.getWeight(item);
        int itemValue = instance.getValue(item);

        if (table[item][currentVolume] != -1)
            return table[item][currentVolume];

        int withOutCurrentItem = calculate(item + 1, currentVolume);
        int withCurrentItem = 0;

        if (currentVolume - itemWeight >= 0) {
            withCurrentItem = itemValue + calculate(item + 1, currentVolume - itemWeight);
        }

        table[item][currentVolume] = Math.max(withOutCurrentItem, withCurrentItem);

        return table[item][currentVolume];
    }

    public Solution backtrack(int bestValue) {
        Solution s = new Solution(instance);
        int n = instance.getSize();
        int W = instance.getWeightLimit();
        int currentVolume = -1;

        for (int j = 0; (j <= W) && (currentVolume == -1); j++) {
            if (table[0][j] == bestValue)
                currentVolume = j;
        }

        for (int i = 0; i < n - 1; i++) {
            int weight = instance.getWeight(i);

            if (currentVolume - instance.getWeight(i) >= 0 && table[i + 1][currentVolume - instance.getWeight(i)] == bestValue - instance.getValue(i)) {
                s.set(i, 1);
                bestValue -= instance.getValue(i);
                currentVolume -= instance.getWeight(i);
            }
        }

        if (bestValue > 0)
            s.set(n - 1, 1);

        return s;
    }
}
@@ -17,25 +17,8 @@
 2;%0A%0A
-/**%0A * O(nW)%0A */%0A
 publ
@@ -261,17 +261,16 @@
 Size();%0A
-%0A
         
@@ -295,16 +295,17 @@
 stance;%0A
+%0A
         
@@ -545,17 +545,21 @@
 lculate(
-0
+n - 1
 , W);%0A%0A 
@@ -606,21 +606,24 @@
 %7D%0A%0A    p
-ublic
+rotected
  int cal
@@ -650,22 +650,22 @@
  current
-Volume
+Weight
 ) %7B%0A    
@@ -681,29 +681,11 @@
 tem 
-%3E= instance.getSize()
+%3C 0
 ) %7B%0A
@@ -849,22 +849,22 @@
 %5Bcurrent
-Volume
+Weight
 %5D != -1)
@@ -902,22 +902,22 @@
 %5Bcurrent
-Volume
+Weight
 %5D;%0A%0A    
@@ -952,33 +952,33 @@
  calculate(item 
-+
+-
  1, currentVolum
@@ -972,22 +972,22 @@
  current
-Volume
+Weight
 );%0A     
@@ -1030,30 +1030,30 @@
  if (current
-Volume
+Weight
  - itemWeigh
@@ -1119,17 +1119,17 @@
 te(item 
-+
+-
  1, curr
@@ -1127,30 +1127,30 @@
 - 1, current
-Volume
+Weight
  - itemWeigh
@@ -1191,22 +1191,22 @@
 %5Bcurrent
-Volume
+Weight
 %5D = Math
@@ -1283,22 +1283,22 @@
 %5Bcurrent
-Volume
+Weight
 %5D;%0A    %7D
@@ -1300,29 +1300,32 @@
     %7D%0A%0A    p
-ublic
+rotected
  Solution ba
@@ -1476,40 +1476,8 @@
 t();
-%0A        int currentVolume = -1;
 %0A%0A  
@@ -1495,265 +1495,50 @@
 int 
-j = 0; (j %3C= W) && (currentVolume == -1); j++) %7B%0A            if (table%5B0%5D%5Bj%5D == bestValue)%0A                currentVolume = j;%0A        %7D%0A%0A        for (int i = 0; i %3C n - 1; i++) %7B%0A            int weight = instance.getWeight(i);%0A%0A            if (currentVolume
+i = n - 1; 0 %3C i; i--) %7B%0A            if (W
  - i
@@ -1578,26 +1578,14 @@
 e%5Bi 
-+
+-
  1%5D%5B
-currentVolume
+W
  - i
@@ -1745,21 +1745,9 @@
     
-currentVolume
+W
  -= 
@@ -1839,21 +1839,17 @@
   s.set(
-n - 1
+0
 , 1);%0A%0A 

Add knapsack2 solver