Can you solve the knapsack problem using dynamic programming?

The knapsack problem can be solved using Dynamic Programming. The knapsack problem is a problem in combinatorial optimization. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Let’s say you are given a set of ‘n‘ items, each item ‘i‘ has some weight ‘w[i]‘ and a value ‘v[i]‘. You are also given a maximum weight ‘W‘. The goal is to choose items with maximum total value such that their total weight is not more than ‘W‘.

We can define a 2D table ‘dp[i][j]‘ where ‘i‘ ranges from 0 to ‘n‘ (the item index) and ‘j‘ ranges from 0 to ‘W‘ (the maximum weight). Each cell ‘dp[i][j]‘ represents the maximum value we can get by considering the first ‘i‘ items and a maximum weight of ‘j‘.

The base case for this problem is ‘dp[i][0]‘ and ‘dp[0][j]‘, which represent the cases where the maximum weight is 0 (we can’t choose any items) and where we don’t consider any items, respectively. In both cases, the maximum value is 0.

Then, for filling in the rest of the table, we follow this recursive relation:

if w[i] > j :
    dp[i][j] = dp[i-1][j]
else:
    dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]])

Explicitly, this recursive relation means that, if the weight of the current item is more than the current maximum weight, we can’t include this item, so the maximum value is the same as the maximum value not considering this item. Otherwise, the maximum value is either the maximum value not considering this item, or the value of this item plus the maximum value we can get considering the remaining weight.

Finally, ‘dp[n][W]‘ will give the maximum total value including the first ‘n‘ items for a maximum weight ‘W‘.

The pseudo code for the DP approach:

function knapSack(W, w, v, n):
   K = array of [n+1][W+1] 
   
   // Build table K[][] in bottom up manner
   for i from 0 to n:
       for w from 0 to W:
           if i==0 or w==0:
               K[i][w] = 0
           else if w[i-1] <= w:
               K[i][w] = max(v[i-1] + K[i-1][w-w[i-1]],  K[i-1][w])
           else:
               K[i][w] = K[i-1][w]
 
   return K[n][W] // this will return the maximum value that can be put in the knapsack of capacity W

This dynamic programming solution for the knapsack problem has a time complexity of ‘O(nW)‘ and a space complexity of ‘O(nW)‘, where ‘n‘ is the number of items and ‘W‘ is the maximum weight. This is because it fills up a 2D table of size ‘nW‘ with the maximum values for each subproblem.