Knapsack 0/1 algorithm - unlimited resources

1
votes

I've run into a thinking trouble and I'm just frustrated. I have a working algorithm of the knapsack problem, using dynamic programming, where I specify

  • Max load
  • Items (their weight)

and the algorithm calculates the optimal fill of the knapsack using those items. But now I need to fill it completely, using least items, but I have unlimited amount of each item. (Those items have weights {1; w1; w2; ...} so it is always possible to complete).

How do I fit this in the 'classic' algorithm?

Thanks

1
algorithmdynamic-programmingknapsack-problem
this prob is equivalent to Coin change prob people.csail.mit.edu/bdean/6.046/dp follow the link for more dynamic programming probs - vikas368
That actually seems exactly like it, yeah. But the links at the page you provided open only a blank window :/ Thanks anyway though - Martin Melka
Nevermind, I typed the address pointed to by the JS command myself. It can be found at people.csail.mit.edu/bdean/6.046/dp/dp_2.swf - Martin Melka

1 Answers

3
votes

Let

  • M = Amount need to fill
  • w[] = Array of weights
  • dp[] = Array of optimal fill(dp[i] contains minimum number of items needed to fill weight i).
 initialize the dp array with INFINITY, dp[0] = 0;
 for(i = 0;i<size of w;i++) {
    for(j = 1;j<=M;j++) {
       if(j-w[i] >= 0) {
          dp[j] = min(dp[j], dp[j-w[i]]+1);
       }
    }
 }

 final solution is the value of dp[M];