01 the knapsack problem with the limit of m items

You should define the following function f(i,j,k) which gives you the maximum value you can get by selecting exactly k items from the first i items (1,2..i) with maximum capacity of j.

according to our definition the transitions will be:

f(i , j , k) = max( t1 , t2 )

t1 = f(i-i , j , k) // here we did not pick the i-th item

t2 = vi + f(i-1 , j - ci , k-1)// here we picked the i-th item

the result to your question will be max( f(n,C,i) ) where i=1,2…n

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top