Dynamic Knapsack Programming

this is a typical Knapsack problem requiring dynamic programming, and there are no restrictions on item delivery. I worked on this for my class, and I tried to work with the algorithm for hours, and I still don't get 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 should take a sorted array of W and V containing the weight and value of the element, respectively, and an integer T representing the maximum weight. For my output, everything is as long as T = 21 does not work, however, after that, it seems to work as a greedy algorithm, and this is not at all what I was hoping for. Any tips would be appreciated, thanks!

+3
source share
2 answers

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

. .

0

, , , localMax ( ). , , , localMax . , . Math.max().

0

All Articles