0-N Knapsack in C++

By Vikhyat Yadav

It's a problem of 2-D DP of knapsack in C++, in which the weight W and a set of n items with some value's, needs to calculate the maximum amount of a profit from these set of items.

We are going to carry only one bag with capacity S (1 <= S <= 1000). You also have N (1<= N <= 1000) items . Unfortunately, we can not fit all of them in the knapsack so, we will have to choose some items. The 0-N knapsack is also known as unbounded knapsack, as there is no restriction while selecting the items any number of times. But it should be less than the capacity of the bag.
We can recursively compute dp[] [],
if(i==0 || w==0)
dp[i][w]=0
else
if(wt[i-1]<=w)
inc=val[i-1]+dp[i][w-wt[i-1]]
exc=dp[i-1][w]
where i & w iterate till no. of items and capacity.
dp[i][w]=max(inc,exc)