Skip to main content

0/1 Knapsack

Learn 0/1 Knapsack (Dynamic Programming, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Each Item Taken At Most Once Given items with weight and value, and a capacity, maximize value - each item is either taken WHOLE or not at all (unlike Fractional Knapsack). dp[i][w] = best value using the first i items with capacity w: either skip item i, or take it (if it fits) and add its value to the best result with the remaining capacity.

More lessons in Dynamic Programming