Programming question

[Bartic]

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

Spoiler!

Code: Select all

Program Knapsack01;
Uses Crt;
Var
  i, j, n, c : integer;
  v, w : array [1..100] of integer;
  t : array [0..100, 0..100] of integer;

Function Max (x, y : integer) : integer;
Begin
  If x > y Then Max := x
  Else Max := y;
End;

Begin
 ClrScr;
 Write ('Capacity of knapsack: ');
 Readln (c);
 Write ('Number of items: ');
 Readln (n);
 Writeln ('Value and weight of every item: ');
 For i := 1 to n Do
   Readln (v [i], w [i]);
 For i := 0 to c Do
   t [0, i] := 0;
 For i := 1 to n Do
   For j := 0 to c Do Begin
     If j >= w [i] Then t [i, j] := Max (t [i - 1, j], t [i - 1, j - w [i]] + v [i])
     Else t [i, j] := t [i - 1, j];
   End;
 Writeln ('Solution: ', t [n, c]);
 Readln;
 Readln;
End.

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.

[EvGa]

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.

[Bartic]

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.