Dynamic Programming: Bounded (1/0) knapsack problem.

This problem is also known as Integer Knapsack Problem (Duplicate Items Forbidden).


During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?


For instance, take Capacity = 10 and
Item Weight Value
1            6      $30
2            3      $14
3            4      $16
4            2      $9


Here repitition is not allowed.


K(w,j) be the max value achievable using knapsack of size w and items 1....j
The answer we seek is K(w,n)


Lets try to express K(w,j) in terms of smaller subproblems
Now here, either j is needed to solve the subproblem or its not needed.
So we have,
K(w,j) = Max { K(w - w[j], j-1) + v[j], K(w, j-1)}


Now algorithm involves, filling out a 2-D table with W+1 rows and n+1 columns.
Time complexity: O(nW).


Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int C = 10;


Output:
Optimal value for integer knapsack: 46