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;
}
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!
source
share