These are the notes for DSA episode 65. You're flying home for Diwali with a 7 kg cabin bag and four gifts: sweets (1 kg, ₹1,000), a saree (3 kg, ₹4,000), a speaker (4 kg, ₹5,000) and a mixer (5 kg, ₹7,000). Packing the best value per kilo first gives the mixer and the sweets, ₹8,000, but the saree and the speaker weigh exactly 7 kg and are worth ₹9,000. We watch greedy fail live, write the correct take-or-skip recursion (Time Limit Exceeded on 60 items), and build the table dp[i][w] = max(dp[i-1][w], val + dp[i-1][w - wt]). Then we shrink it to one row and see why the capacity loop must run down. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problem, in real life
| Packing the cabin bag | In code |
|---|---|
| The airline's 7 kg limit | capacity W = 7 |
| Gifts, one of each | items 0 … n-1 |
| Weight of a gift | wt[i] |
| What it's worth (₹ thousands) | val[i] |
| Pack it or leave it | 1 (take) or 0 (skip): 0/1 |
| Most value that fits | the answer |
Every word, from zero
- Knapsack: an old word for a backpack. The "knapsack problem" is any problem of choosing items under a weight limit.
- 0/1 knapsack: each item is taken once (1) or not at all (0). No halves, no repeats.
- Fractional knapsack: items can be cut (rice, oil). There, best value per kg first is optimal.
- Unbounded knapsack: items can be reused any number of times (coin change, episode 64).
- Greedy: always make the choice that looks best right now, never reconsider.
- Subset: any selection of the items;
nitems have2^nsubsets. - State: the few numbers that fully describe a sub-problem; here
(i, w): the firstiitems and capacityw. - Memoization (top-down): the recursion plus a notebook of answers already computed.
- Tabulation (bottom-up): filling a table from the smallest sub-problems upward.
- Space optimisation (rolling array): keeping only the row(s) the next row needs.
- Pseudo-polynomial:
O(n × W)looks polynomial, butWis a number, not a count; a huge capacity makes the table huge.
Problem statement
Given n items with weights wt[i] and values val[i] and a bag of capacity W, choose a subset with total weight ≤ W and the largest total value. Each item can be used at most once.
| wt | val | W | Answer |
|---|---|---|---|
[1, 3, 4, 5] |
[1, 4, 5, 7] |
7 | 9 (3 kg + 4 kg) |
[10, 20, 30] |
[60, 100, 120] |
50 | 220 (20 + 30) |
[4, 5] |
[10, 20] |
0 | 0 (nothing fits) |
[5] |
[10] |
4 | 0 (item heavier than the bag) |
[1, 5] |
[10, 1] |
3 | 10 |
Typical constraints: 1 ≤ n ≤ 1000, 1 ≤ W ≤ 1000, 1 ≤ wt[i], val[i] ≤ 1000.
Greedy fails: best value per kilo first
Sort by val / wt, take everything that still fits.
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
Integer[] idx = new Integer[wt.length];
for (int i = 0; i < wt.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Double.compare((double) val[b] / wt[b], (double) val[a] / wt[a]));
int total = 0;
for (int i : idx)
if (wt[i] <= W) {
W -= wt[i];
total += val[i];
}
return total;
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
}
}
8
160
On the classic example the 10 kg item has the best ratio (6 per kg), so greedy takes 10 + 20 = 30 kg (160) and then the 30 kg item no longer fits. The right answer leaves the "best" item out: 20 + 30 kg = 220. Greedy is optimal only for the fractional knapsack.
Obvious correct idea: take or skip every item
For item i: skip it (capacity unchanged) or, if it fits, take it (gain val[i], capacity drops by wt[i]). Keep the better.
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
return best(wt, val, 0, W);
}
static int best(int[] wt, int[] val, int i, int W) {
if (i == wt.length) return 0;
int skip = best(wt, val, i + 1, W);
if (wt[i] > W) return skip;
int take = val[i] + best(wt, val, i + 1, W - wt[i]);
return Math.max(skip, take);
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
System.out.println(knapsack(new int[]{4, 5}, new int[]{10, 20}, 0));
System.out.println(knapsack(new int[]{5}, new int[]{10}, 4));
System.out.println(knapsack(new int[]{1, 5}, new int[]{10, 1}, 3));
}
}
9
220
0
0
10
Correct, but with 60 items (weights 1 to 10, capacity 200):
int n = 60;
int[] wt = new int[n], val = new int[n];
for (int i = 0; i < n; i++) {
wt[i] = i % 10 + 1;
val[i] = (i * 37) % 50 + 1;
}
long t0 = System.nanoTime();
int best = knapsack(wt, val, 200);
System.out.println("60 items: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
Time Limit Exceeded
Why is it slow?
Every item doubles the number of paths: up to 2^60 (more than 10^18). But a call depends only on two numbers, (i, W left), and different choices reach the same pair (skip one 2 kg item and take another, or the reverse). There are only n × (W + 1) = 60 × 201 = 12,060 different questions. Solving each once is the whole idea of DP.
The key insight: the DP table
- State:
dp[i][w]= best value using only the firstiitems with capacityw. - Skip item i:
dp[i-1][w](the cell directly above). - Take item i (if
wt[i-1] ≤ w):val[i-1] + dp[i-1][w - wt[i-1]](one row up,wtto the left). dp[i][w] = max(skip, take). Base: row 0 (no items) is all zeros.- Answer:
dp[n][W], the bottom-right cell.
By hand: a 4 kg bag, A (1 kg, ₹15), B (3 kg, ₹20), C (4 kg, ₹30)
| items \ w | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| none | 0 | 0 | 0 | 0 | 0 |
| A (1, 15) | 0 | 15 | 15 | 15 | 15 |
| B (3, 20) | 0 | 15 | 15 | 20 | 35 = max(15, 20 + dp[A][1]) |
| C (4, 30) | 0 | 15 | 15 | 20 | 35 = max(35, 30 + dp[B][0]) |
Answer 35: A and B together beat C alone.
Solution in Java: the 2D table
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w];
if (wt[i - 1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
return dp[n][W];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
System.out.println(knapsack(new int[]{4, 5}, new int[]{10, 20}, 0));
System.out.println(knapsack(new int[]{5}, new int[]{10}, 4));
System.out.println(knapsack(new int[]{1, 5}, new int[]{10, 1}, 3));
}
}
9
220
0
0
10
The 60 items that timed out, and 1,000 items with capacity 1,000:
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w];
if (wt[i - 1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
return dp[n][W];
}
public static void main(String[] args) {
int n = 60;
int[] wt = new int[n], val = new int[n];
for (int i = 0; i < n; i++) {
wt[i] = i % 10 + 1;
val[i] = (i * 37) % 50 + 1;
}
long t0 = System.nanoTime();
int best = knapsack(wt, val, 200);
System.out.println("60 items: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
int m = 1000;
int[] w2 = new int[m], v2 = new int[m];
for (int i = 0; i < m; i++) {
w2[i] = (i * 31) % 97 + 1;
v2[i] = (i * 53) % 101 + 1;
}
long t1 = System.nanoTime();
int b2 = knapsack(w2, v2, 1000);
System.out.println("1000 items, W = 1000: " + b2 + ", " + (System.nanoTime() - t1) / 1000000 + " ms");
}
}
60 items: 1330, 1 ms
1000 items, W = 1000: 8209, 12 ms
Top-down: the recursion plus a notebook
-1 marks "not solved yet" (values are never negative, so it can't be a real answer).
import java.util.*;
public class Main {
static int[][] memo;
static int knapsack(int[] wt, int[] val, int W) {
memo = new int[wt.length][W + 1];
for (int[] row : memo) Arrays.fill(row, -1);
return best(wt, val, 0, W);
}
static int best(int[] wt, int[] val, int i, int W) {
if (i == wt.length) return 0;
if (memo[i][W] != -1) return memo[i][W];
int skip = best(wt, val, i + 1, W);
int take = wt[i] <= W ? val[i] + best(wt, val, i + 1, W - wt[i]) : 0;
return memo[i][W] = Math.max(skip, take);
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
int n = 60;
int[] wt = new int[n], val = new int[n];
for (int i = 0; i < n; i++) {
wt[i] = i % 10 + 1;
val[i] = (i * 37) % 50 + 1;
}
long t0 = System.nanoTime();
int best = knapsack(wt, val, 200);
System.out.println("60 items: " + best + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
9
220
60 items: 1330, 1 ms
Which items? Walk the table back
Start at dp[n][W]. If dp[i][w] != dp[i-1][w], item i was taken: record it and move left by its weight. Otherwise it was skipped.
import java.util.*;
public class Main {
static void pack(String[] name, int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w];
if (wt[i - 1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
List<String> bag = new ArrayList<>();
for (int i = n, w = W; i > 0; i--)
if (dp[i][w] != dp[i - 1][w]) {
bag.add(name[i - 1]);
w -= wt[i - 1];
}
System.out.println(bag + ", worth " + dp[n][W]);
}
public static void main(String[] args) {
String[] gifts = {"sweets", "saree", "speaker", "mixer"};
pack(gifts, new int[]{1, 3, 4, 5}, new int[]{1000, 4000, 5000, 7000}, 7);
pack(gifts, new int[]{1, 3, 4, 5}, new int[]{1000, 4000, 5000, 7000}, 10);
}
}
[speaker, saree], worth 9000
[mixer, speaker, sweets], worth 13000
The list comes out last item first because we walk from the bottom row up.
One row: the capacity loop runs DOWN
Row i reads only row i - 1, so one array dp[w] is enough, updated item by item. When we compute dp[w] we read dp[w - wt], which must still be the old value (before this item). Going from W down to wt, the cells on the left haven't been touched yet.
| One item: 10 kg, ₹60 | dp[0] | dp[10] | dp[20] | dp[30] |
|---|---|---|---|---|
| before | 0 | 0 | 0 | 0 |
| loop up (wrong) | 0 | 60 | 120 | 180 (item packed 3 times) |
| loop down (right) | 0 | 60 | 60 | 60 |
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++)
for (int w = W; w >= wt[i]; w--)
dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 3, 4, 5}, new int[]{1, 4, 5, 7}, 7));
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
System.out.println(knapsack(new int[]{4, 5}, new int[]{10, 20}, 0));
System.out.println(knapsack(new int[]{5}, new int[]{10}, 4));
System.out.println(knapsack(new int[]{1, 5}, new int[]{10, 1}, 3));
int m = 1000;
int[] w2 = new int[m], v2 = new int[m];
for (int i = 0; i < m; i++) {
w2[i] = (i * 31) % 97 + 1;
v2[i] = (i * 53) % 101 + 1;
}
long t1 = System.nanoTime();
int b2 = knapsack(w2, v2, 1000);
System.out.println("1000 items, W = 1000: " + b2 + ", " + (System.nanoTime() - t1) / 1000000 + " ms");
}
}
9
220
0
0
10
1000 items, W = 1000: 8209, 6 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// 0/1 knapsack: one row, the capacity loop runs DOWN so each item is used once.
int knapsack(const vector<int>& wt, const vector<int>& val, int W) {
vector<int> dp(W + 1, 0);
for (size_t i = 0; i < wt.size(); i++)
for (int w = W; w >= wt[i]; w--)
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
int main() {
cout << knapsack({1, 3, 4, 5}, {1, 4, 5, 7}, 7) << "\n";
cout << knapsack({10, 20, 30}, {60, 100, 120}, 50) << "\n";
cout << knapsack({4, 5}, {10, 20}, 0) << "\n";
cout << knapsack({5}, {10}, 4) << "\n";
cout << knapsack({1, 5}, {10, 1}, 3) << "\n";
vector<int> w2(1000), v2(1000);
for (int i = 0; i < 1000; i++) { w2[i] = (i * 31) % 97 + 1; v2[i] = (i * 53) % 101 + 1; }
cout << knapsack(w2, v2, 1000) << "\n";
}
9
220
0
0
10
8209
The same solution in Python
# 0/1 knapsack: one row, the capacity loop runs DOWN so each item is used once.
def knapsack(wt, val, W):
dp = [0] * (W + 1)
for w_i, v_i in zip(wt, val):
for w in range(W, w_i - 1, -1):
dp[w] = max(dp[w], dp[w - w_i] + v_i)
return dp[W]
print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(knapsack([10, 20, 30], [60, 100, 120], 50))
print(knapsack([4, 5], [10, 20], 0))
print(knapsack([5], [10], 4))
print(knapsack([1, 5], [10, 1], 3))
w2 = [(i * 31) % 97 + 1 for i in range(1000)]
v2 = [(i * 53) % 101 + 1 for i in range(1000)]
print(knapsack(w2, v2, 1000))
9
220
0
0
10
8209
Three real bugs
Bug 1: one row, loop going up. Each item can be reused, so it becomes the unbounded knapsack.
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < wt.length; i++)
for (int w = wt[i]; w <= W; w++)
dp[w] = Math.max(dp[w], dp[w - wt[i]] + val[i]);
return dp[W];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
}
}
300
The 10 kg item (₹60) was packed five times: 300 instead of 220. Fix: for (int w = W; w >= wt[i]; w--).
Bug 2: the table one column short.
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n + 1][W];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w];
if (wt[i - 1] <= w)
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
return dp[n][W];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{10, 20, 30}, new int[]{60, 100, 120}, 50));
}
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50
at Main.knapsack(Main.java:9)
at Main.main(Main.java:16)
Capacities run 0 … W: that's W + 1 columns.
Bug 3: not copying the skip value when the item doesn't fit.
import java.util.*;
public class Main {
static int knapsack(int[] wt, int[] val, int W) {
int n = wt.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++)
for (int w = 0; w <= W; w++) {
if (wt[i - 1] <= w)
dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
}
return dp[n][W];
}
public static void main(String[] args) {
System.out.println(knapsack(new int[]{1, 5}, new int[]{10, 1}, 3));
}
}
0
Item 2 (5 kg) never fits in 3 kg, so row 2 stayed all zeros and item 1's value (10) was lost. Fix: dp[i][w] = dp[i - 1][w] first, then try taking.
Complexity
| Approach | Time | Space | Big input |
|---|---|---|---|
| Best value per kg | O(n log n) | O(n) | wrong for whole items |
| Take or skip (every subset) | O(2^n) | O(n) stack | 60 items: Time Limit Exceeded |
| DP table (2D) | O(n × W) | O(n × W) | 1,000 × 1,000: ~12 ms |
| Top-down memo | O(n × W) | O(n × W) + O(n) stack | |
| One row (1D) | O(n × W) | O(W) | 1,000 × 1,000: ~6 ms |
O(n × W) is pseudo-polynomial: it grows with the value of W. With W = 10^9, the table is impossible; then a different state (e.g. dp[value] = least weight) or meet-in-the-middle for small n is used.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Best value per kg first | 8 instead of 9; 160 instead of 220 |
greedy only works for fractional items | DP over (item, capacity) |
| One row, loop going up | 300 instead of 220 |
an item reused | w = W down to wt[i] |
new int[n + 1][W] |
ArrayIndexOutOfBoundsException: Index 50 out of bounds for length 50 |
capacities are 0 … W |
W + 1 columns |
| No copy when the item doesn't fit | 0 instead of 10 |
skip value lost | dp[i][w] = dp[i-1][w] first |
wt[i] instead of wt[i - 1] in the 2D table |
wrong answers / out of bounds | row i is item i - 1 |
keep the off-by-one consistent |
int for big totals |
overflow | values × items > 2^31 | long |
Mini project: pack the bag
The pack program above is the mini project: change the gifts, the weights and the bag limit (try 10 kg and 15 kg) and print which gifts to take. Extension: also print the total weight used, and the weight left over.
Practice
1. Partition Equal Subset Sum (LeetCode 416). Can the array be split into two parts with equal sums?
Solution
A 0/1 knapsack of booleans: can some items fill exactly W = sum / 2? Loop down, as always.
# Partition Equal Subset Sum (LeetCode 416): a 0/1 knapsack of booleans with W = sum / 2.
def can_partition(nums):
total = sum(nums)
if total % 2:
return False
W = total // 2
dp = [True] + [False] * W
for x in nums:
for w in range(W, x - 1, -1):
dp[w] = dp[w] or dp[w - x]
return dp[W]
print(can_partition([1, 5, 11, 5]), can_partition([1, 2, 3, 5]))
True False
2. Target Sum (LeetCode 494). Put + or - before every number; count the ways to reach target.
Solution
If P is the sum of the + numbers, P - (total - P) = target, so P = (total + target) / 2: count subsets with that sum.
# Target Sum (LeetCode 494): choose the "+" numbers P; P - (total - P) = target, so P = (total + target) / 2.
def find_target_sum_ways(nums, target):
total = sum(nums)
if abs(target) > total or (total + target) % 2:
return 0
W = (total + target) // 2
dp = [1] + [0] * W
for x in nums:
for w in range(W, x - 1, -1):
dp[w] += dp[w - x]
return dp[W]
print(find_target_sum_ways([1, 1, 1, 1, 1], 3), find_target_sum_ways([1], 1))
5 1
3. Last Stone Weight II (LeetCode 1049). Smash stones together; the smallest possible last stone.
Solution
Split into two piles as equal as possible: the largest reachable subset sum ≤ total / 2.
# Last Stone Weight II (LeetCode 1049): split the stones into two piles as equal as possible.
def last_stone_weight_ii(stones):
total = sum(stones)
W = total // 2
dp = [True] + [False] * W
for s in stones:
for w in range(W, s - 1, -1):
dp[w] = dp[w] or dp[w - s]
best = max(w for w in range(W + 1) if dp[w])
return total - 2 * best
print(last_stone_weight_ii([2, 7, 4, 1, 8, 1]), last_stone_weight_ii([31, 26, 33, 21, 40]))
1 5
4. Ones and Zeroes (LeetCode 474). A knapsack with two capacities (zeros and ones): dp[z][o], both loops running down.
Quick quiz
wt = [2, 3, 4, 5], val = [3, 4, 5, 6], W = 5. Best value? A) 6 B) 7 C) 8 D) 9
Answer
B) 7: the 2 kg and 3 kg items, 3 + 4. The 5 kg item alone is only 6.
Interview questions
- Why does greedy fail? Items are whole; the best-ratio item can block a better combination (
[10, 20, 30], W 50). - State and recurrence?
dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]]), row 0 = 0. - Why does the 1D loop run down?
dp[w - wt]must still hold the previous item's row; going up would reuse the item. - 0/1 vs unbounded knapsack? Once vs any number of times; in one row, loop down vs loop up.
- Complexity? Is it polynomial? O(n × W) time, O(W) space; pseudo-polynomial, because it depends on the value of
W. - How do you recover the chosen items? Keep the 2D table and walk back from
dp[n][W].
Glossary
| Term | Meaning |
|---|---|
| Knapsack | A bag with a weight limit; choosing items under a limit |
| 0/1 knapsack | Each item taken once or not at all |
| Fractional knapsack | Items can be cut; greedy by ratio is optimal |
| Unbounded knapsack | Items reusable (coin change) |
| Greedy | Pick what looks best now, never reconsider |
| Subset | Any selection of items (2^n of them) |
| State | (i, w): first i items, capacity w |
| Recurrence | max(skip, take) |
| Memoization | Top-down recursion with a notebook |
| Tabulation | Bottom-up table filling |
| Rolling array | Keeping one row instead of the whole table |
| Pseudo-polynomial | Polynomial in the value of an input number, not its size |
Summary
- 0/1 knapsack: whole items, each once, a weight limit, maximum value.
- Best value per kg fails (
8instead of9,160instead of220); take-or-skip recursion is right butO(2^n). dp[i][w] = max(dp[i-1][w], val + dp[i-1][w - wt]), answerdp[n][W], walk back for the items.- One row: loop the capacity down. Loop up = unbounded knapsack.
O(n × W)time,O(W)space. Next episode: longest increasing subsequence, from O(n²) to O(n log n).