Info

0/1 Knapsack is a Dynamic Programming technique to get maximum "value" from N items in a knapsack with a limited capacity W. Read More about 0/1 Knapsack on cp-algorithms.

Enter the weight array, value array, and the capacity of the knapsack to see how the 0/1 Knapsack DP table is filled step by step.

dp[i][j]: maximum value from first i items with j capacity

Recurrence:

Take current item: dp[i][j-wt[i-1]] + val[i-1]

Dont take current item: dp[i-1][j]

dp[i][j] = MAX(Take, Dont take)

So, for each cell (i, j) we check (i-1, j-wt[i-1]) and (i, j-1), and consider the cell that gives us larger value.

🍎Red Cell: Indicates it was not considered

🍏Green Cell: Indicates it was considered

This visualization shows the take vs dont take decision at each cell. The same DP idea is used directly or indirectly in many problems like subset sum, coin change, and other optimization-based DP problems.

Here is a list of problems based on 0/1 Knapsack

For queries, contact me through GitHub or LinkedIn