SyntaxPilot
Courses/DSA and Coding Problems/Lesson 65
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 65 of 90

0/1 knapsack

queued

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; n items have 2^n subsets.
  • State: the few numbers that fully describe a sub-problem; here (i, w): the first i items and capacity w.
  • 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, but W is 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

  1. State: dp[i][w] = best value using only the first i items with capacity w.
  2. Skip item i: dp[i-1][w] (the cell directly above).
  3. Take item i (if wt[i-1] ≤ w): val[i-1] + dp[i-1][w - wt[i-1]] (one row up, wt to the left).
  4. dp[i][w] = max(skip, take). Base: row 0 (no items) is all zeros.
  5. 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

  1. Why does greedy fail? Items are whole; the best-ratio item can block a better combination ([10, 20, 30], W 50).
  2. State and recurrence? dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]]), row 0 = 0.
  3. Why does the 1D loop run down? dp[w - wt] must still hold the previous item's row; going up would reuse the item.
  4. 0/1 vs unbounded knapsack? Once vs any number of times; in one row, loop down vs loop up.
  5. Complexity? Is it polynomial? O(n × W) time, O(W) space; pseudo-polynomial, because it depends on the value of W.
  6. 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 (8 instead of 9, 160 instead of 220); take-or-skip recursion is right but O(2^n).
  • dp[i][w] = max(dp[i-1][w], val + dp[i-1][w - wt]), answer dp[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).