Knapsack Dynamic Programming

3
votes

this is a typical Knapsack problem requiring dynamic programming and there is no constraint on the supply of items. I've been working on this for my class and I tried to play around with the algorithm for hours and I'm still not getting there.

public static int fitBackPack(int[] W, int[] V, int T){
    int[] Opt = new int[T+1];
    Opt[0]=0;
    for (int i=1; i<=T; i++){
        int localMax=0;
        int globalMax=0;
        for (int j=0; j<W.length; j++){
            if (W[j]<=i){
                localMax = (T%W[j]<=W[j]) ?  V[j] : V[j]+Opt[T-W[j]];
                globalMax = (localMax>=globalMax) ? localMax : globalMax;
            }
        }
        Opt[i]=globalMax;
    }
    //debugging purposes
    for (int k=0; k<Opt.length; k++){
        System.out.println("Opt["+k+"] = "+Opt[k]);
    }
    return Opt[T];
}

This method is supposed to take a sorted array of W and V, containing the weight and the value of the item respectively, and an integer T representing the max weight. For my output, everything up until T=21 works, however, after that it just seems to be working like a greedy algorithm, which is completely not what I was hoping for. Any hints will be appreciated, thanks!

2
javadynamic-programmingknapsack-problem

2 Answers

0
votes

Hints: (x % y <= y) == true

Every now and then a truth table through your conditions with test cases will help you find these. Better still set up some automated tests for general usage and edge cases.

0
votes

Since your algorithm is acting like a greedy one, you problem is probably on the calculation of localMax (since greedy algorithms look for the highest local value). By looking at your code, you seem to be getting localMax in the wrong way. Hint, see Math.max() function.