Bug in simple dynamic programming algorithm (classic knapsack)

Question

I looked at http://rosettacode.org/wiki/Knapsack_problem/0-1 to do the basic knapsack dynamic programming problem, and I got a working solution (knapsack1()), but when I tried a different solution (knapsack2()) I feel like I am off-by-one somewhere because I am not getting the correct value.

The code in question is the method knapsack2, at the bottom. I'm sure the issue is small, but I feel absurd because I can't find the problem. The correct answer should be 1030 and not 880.

(I know that an array of size [n][S] should be enough, as shown in knapsack1(), which works, but knapsack2() doesn't oddly.)

Thanks in advance for anyone who looks through this.

/**
 * http://rosettacode.org/wiki/Knapsack_problem/0-1
 */
public class Knapsack {

    public static void main(String[] args) {
        int n = 22;
        int S = 400;
        int s[] = new int[22];
        int v[] = new int[22];
        int i = 0;
        s[i] = 9;
        v[i] = 150;
        i++;
        s[i] = 13;
        v[i] = 35;
        i++;
        s[i] = 153;
        v[i] = 200;
        i++;
        s[i] = 50;
        v[i] = 160;
        i++;
        s[i] = 15;
        v[i] = 60;
        i++;
        s[i] = 68;
        v[i] = 45;
        i++;
        s[i] = 27;
        v[i] = 60;
        i++;
        s[i] = 39;
        v[i] = 40;
        i++;
        s[i] = 23;
        v[i] = 30;
        i++;
        s[i] = 52;
        v[i] = 10;
        i++;
        s[i] = 11;
        v[i] = 70;
        i++;
        s[i] = 32;
        v[i] = 30;
        i++;
        s[i] = 24;
        v[i] = 15;
        i++;
        s[i] = 48;
        v[i] = 10;
        i++;
        s[i] = 73;
        v[i] = 40;
        i++;
        s[i] = 42;
        v[i] = 70;
        i++;
        s[i] = 43;
        v[i] = 75;
        i++;
        s[i] = 22;
        v[i] = 80;
        i++;
        s[i] = 7;
        v[i] = 20;
        i++;
        s[i] = 18;
        v[i] = 12;
        i++;
        s[i] = 4;
        v[i] = 50;
        i++;
        s[i] = 30;
        v[i] = 10;

        System.out.println("--Given items with these values--");
        System.out.println("[item, weight (dag), value]");
        System.out.println("map  9   150");
        System.out.println("compass  13  35");
        System.out.println("water    153     200");
        System.out.println("sandwich     50  160");
        System.out.println("glucose  15  60");
        System.out.println("tin  68  45");
        System.out.println("banana   27  60");
        System.out.println("apple    39  40");
        System.out.println("cheese   23  30");
        System.out.println("beer     52  10");
        System.out.println("suntan cream     11  70");
        System.out.println("camera   32  30");
        System.out.println("T-shirt  24  15");
        System.out.println("trousers     48  10");
        System.out.println("umbrella     73  40");
        System.out.println("waterproof trousers  42  70");
        System.out.println("waterproof overclothes   43  75");
        System.out.println("note-case    22  80");
        System.out.println("sunglasses   7   20");
        System.out.println("towel    18  12");
        System.out.println("socks    4   50");
        System.out.println("book     30  10");
        System.out.println("--The max value you can achieve in your knapsack--");
        System.out.println(knapsack2(n, S, s, v));
        // proper value should be 1030, from website
    }

    /**
     * @param n items
     * @param S bag size/capacity
     * @param s array where s[i] is size/weight of item at index i
     * @param v array where v[i] is value of item at index i
     * @return best/max value possible
     */
    @SuppressWarnings("unused")
    private static int knapsack1(int n, int S, int s[], int v[]) {
        int dp[][] = new int[n][S];
        for (int i=n-1; i >= 0; i--) { // # items being left out + 1
            for (int j=0; j < S; j++) { // size/weight + 1
                if (i == n-1) {
                    dp[i][j] = 0;
                } else {
                    int choices[] = {0,0};
                    choices[0] = dp[i+1][j];
                    if (j >= s[i])
                        choices[1] = v[i] + dp[i+1][j-s[i]];
                    dp[i][j] = max(choices);
                }
            }
        }
        return dp[0][S-1];
    }

    private static int max(int choices[]) {
        if (choices[0] > choices[1])
            return choices[0];
        else
            return choices[1];
    }

    /**
     * @param n items
     * @param S bag size/capacity
     * @param s array where s[i] is size/weight of item at index i
     * @param v array where v[i] is value of item at index i
     * @return best/max value possible
     */
//  @SuppressWarnings("unused")
    private static int knapsack2(int n, int S, int s[], int v[]) {
        int dp[][] = new int[n][S]; // dp[i][j] holds max value using i items and not exceeding weight j+1 
        for (int i=0; i < n; i++) { // # items. don't need to reach n because we assume we can fit at most n-1 items.
            for (int j=0; j < S; j++) { // size/weight+1
                if (i == 0) {
                    dp[i][j] = 0;
                } else {
                    int choices[] = {0,0};
                    choices[0] = dp[i-1][j];
                    if (j >= s[i])
                        choices[1] = v[i] + dp[i-1][j-s[i]];
                    dp[i][j] = max(choices);
                }
            }
        }
        return dp[n-1][S-1]; // TODO: WHY IS THIS 880 AND NOT 1030?
    }
}

Answer 1

Both your knapsack functions have issues. Both won't pass the simple test - S=1 n=1 s[0]=1 v[0]=10. The answer should be 10 but your code will return 0.

You can see that the issue are in the lines if (i==(n-1)) (knapsack1) or if (i==0) (knapsack2).

Also, you will see issues because of condition if (j >= s[i]. Your j starts at 0 so, if S was 1, you'll never be able to the item with s[i] == 1 because j will never reach 1.

Hope this helps. Good luck.