##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
The Knapsack problem asks: given items, each with a weight and value, what's the maximum value you can carry in a bag with capacity ?
The "" means you either take an item completely or leave it behind. No splitting allowed. You can't take half a laptop.
Example: You have items:
Apply what you learned by solving the practice problem for 0/1 Knapsack.
Go to Practice ProblemWith capacity , your best choice is items A + B for total value .
Real applications: budget allocation across projects, loading cargo onto trucks, selecting features under time constraints.
For each item, you face a binary decision: take it or skip it.
If you take item :
If you skip item :
You want the combination that maximizes total value without exceeding capacity .
Think of it recursively. At each step, you compare: "What's better? Taking this item (if it fits) or skipping it?" The answer depends on what you can do with the remaining items and remaining capacity.
You define as the maximum value achievable using the first items with capacity .
Base case: for all . With zero items, you get zero value.
Transition: For each item with weight and value :
The first term is skipping item . The second term is taking it (only valid when ).
You build the table row by row. Each cell asks: "Given this capacity and these items available, what's the best I can do?" The answer at gives your final result.
Here's the complete D dynamic programming solution:
function knapsack(weights, values, W):
n = length(weights)
dp = 2D array of size (n+1) x (W+1), initialized to 0
for i from 1 to n:
for w from 0 to W:
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
Reconstructing the solution: Start at . If , item was taken. Move to . Otherwise, move to . Repeat until .
You can reduce space from to using a D array.
The trick: iterate capacity backwards. This prevents overwriting values you still need.
function knapsack(weights, values, W):
n = length(weights)
dp = array of size (W+1), initialized to 0
for i from 0 to n-1:
for w from W down to weights[i]:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
Why backwards? When processing item , you need from the previous row. Going right-to-left ensures you read old values before updating them.
Complexity: time, space.