Silkroad Online Forums

Hey guys. I was wondering if anyone here knows something about programming (I assume at least someone does). I was trying to figure Knapsack problem out, and I did. I figured out the 0/1 Knapsack problem, as I watched an explanation on YouTube. I did write a code myself after hearing an explanation (there was no pseudo code). Here it is (it's in Pascal, don't flame me):


Now, my question is: Does anybody here has a link to the explanation of Knapsack problem with infinite number of items or has a code for it? It doesn't matter what programming language it is, although I prefer pseudo code.

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).

Code: Select all

 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];

http://people.csail.mit.edu/bdean/6.046/dp/dp_2.swf

The above may help. I grabbed it off stackoverflow.

EvGa wrote:

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).

Code: Select all

 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];

http://people.csail.mit.edu/bdean/6.046/dp/dp_2.swf

The above may help. I grabbed it off stackoverflow.

I thought of something similar. I will check it. Thanks.