Chapter 27 of 30

Dynamic Programming — Knapsack & Subsets

Master the 0-1 knapsack, unbounded knapsack, subset sum variants, and bitmask DP.

The 0-1 Knapsack ProblemUnbounded KnapsackSubset Sum & Knapsack VariantsBitmask DP

Dynamic Programming — Knapsack & Subsets

The knapsack problem and its variants are the most common DP patterns. Once you understand them, you can solve a wide variety of optimization problems.

The 0-1 Knapsack Problem

Given n items, each with weight w[i] and value v[i], and a knapsack of capacity W, maximize the total value of items you can carry (each item used at most once).

DP Formulation

code

dp[i][w] = maximum value using items 0..i with capacity w
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])

Implementation

hljs cpp

vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        dp[i][w] = dp[i - 1][w];  // don't take item i
        if (w >= wt[i - 1]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
        }
    }
}
int answer = dp[n][W];

Space-Optimized (1D)

hljs cpp

vector<int> dp(W + 1, 0);

for (int i = 0; i < n; i++) {
    for (int w = W; w >= wt[i]; w--) {  // reverse order!
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    }
}
int answer = dp[W];

Why reverse order? In 0-1 knapsack, each item is used at most once. Processing from right to left ensures we don't use the same item twice.

Unbounded Knapsack

Each item can be used unlimited times:

hljs cpp

vector<int> dp(W + 1, 0);

for (int w = 1; w <= W; w++) {
    for (int i = 0; i < n; i++) {
        if (wt[i] <= w) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
}
int answer = dp[W];

Key difference: iterate capacity from left to right (allowing reuse).

Subset Sum & Knapsack Variants

Subset Sum

Can you select elements that sum to exactly target?

hljs cpp

vector<bool> dp(target + 1, false);
dp[0] = true;

for (int x : a) {
    for (int s = target; s >= x; s--) {
        dp[s] = dp[s] || dp[s - x];
    }
}
bool possible = dp[target];

Count Subsets with Sum = Target

hljs cpp

vector<long long> dp(target + 1, 0);
dp[0] = 1;

for (int x : a) {
    for (int s = target; s >= x; s--) {
        dp[s] += dp[s - x];
    }
}
long long count = dp[target];

Minimum Number of Elements to Reach Target

hljs cpp

vector<int> dp(target + 1, INT_MAX);
dp[0] = 0;

for (int s = 1; s <= target; s++) {
    for (int x : a) {
        if (x <= s && dp[s - x] != INT_MAX) {
            dp[s] = min(dp[s], dp[s - x] + 1);
        }
    }
}
int answer = dp[target];  // INT_MAX if impossible

Coin Change

hljs cpp

// Minimum coins to make amount
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

for (int coin : coins) {
    for (int s = coin; s <= amount; s++) {
        if (dp[s - coin] != INT_MAX) {
            dp[s] = min(dp[s], dp[s - coin] + 1);
        }
    }
}
int answer = dp[amount];

Bitmask DP

Use a bitmask to represent which elements have been used:

Travelling Salesman Problem (TSP)

hljs cpp

// dp[mask][i] = minimum cost to visit all cities in mask, ending at i
const int INF = 1e9;
int dp[1 << n][n];

memset(dp, INF, sizeof(dp));
dp[1][0] = 0;  // start at city 0

for (int mask = 1; mask < (1 << n); mask++) {
    for (int u = 0; u < n; u++) {
        if (!(mask & (1 << u))) continue;
        if (dp[mask][u] == INF) continue;
        for (int v = 0; v < n; v++) {
            if (mask & (1 << v)) continue;
            int newMask = mask | (1 << v);
            dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
        }
    }
}

int ans = INF;
for (int u = 0; u < n; u++) {
    ans = min(ans, dp[(1 << n) - 1][u] + dist[u][0]);
}

Assignment Problem

hljs cpp

// Assign n tasks to n workers, minimize total cost
// dp[mask] = minimum cost for the tasks in mask
vector<int> dp(1 << n, INF);
dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    int taskIndex = __builtin_popcount(mask);  // which task to assign next
    for (int worker = 0; worker < n; worker++) {
        int newMask = mask | (1 << worker);
        dp[newMask] = min(dp[newMask], dp[mask] + cost[taskIndex][worker]);
    }
}

Summary

0-1 knapsack: process items in reverse weight order (no reuse)
Unbounded knapsack: process items in forward weight order (unlimited reuse)
Subset sum: dp[s] = dp[s] || dp[s - x] for each element
Bitmask DP: O(2ⁿ × n) — use for n ≤ 20
All knapsack variants follow the same pattern: iterate items, iterate capacity

Ch 26: Dynamic Programming — Foundations Ch 28: Backtracking & Meet-in-the-Middle

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 27 of 30

Dynamic Programming — Knapsack & Subsets

Master the 0-1 knapsack, unbounded knapsack, subset sum variants, and bitmask DP.

The 0-1 Knapsack ProblemUnbounded KnapsackSubset Sum & Knapsack VariantsBitmask DP

Dynamic Programming — Knapsack & Subsets

The knapsack problem and its variants are the most common DP patterns. Once you understand them, you can solve a wide variety of optimization problems.

The 0-1 Knapsack Problem

Given n items, each with weight w[i] and value v[i], and a knapsack of capacity W, maximize the total value of items you can carry (each item used at most once).

DP Formulation

code

dp[i][w] = maximum value using items 0..i with capacity w
dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])

Implementation

hljs cpp

vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        dp[i][w] = dp[i - 1][w];  // don't take item i
        if (w >= wt[i - 1]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - wt[i - 1]] + val[i - 1]);
        }
    }
}
int answer = dp[n][W];

Space-Optimized (1D)

hljs cpp

vector<int> dp(W + 1, 0);

for (int i = 0; i < n; i++) {
    for (int w = W; w >= wt[i]; w--) {  // reverse order!
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    }
}
int answer = dp[W];

Why reverse order? In 0-1 knapsack, each item is used at most once. Processing from right to left ensures we don't use the same item twice.

Unbounded Knapsack

Each item can be used unlimited times:

hljs cpp

vector<int> dp(W + 1, 0);

for (int w = 1; w <= W; w++) {
    for (int i = 0; i < n; i++) {
        if (wt[i] <= w) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
}
int answer = dp[W];

Key difference: iterate capacity from left to right (allowing reuse).

Subset Sum & Knapsack Variants

Subset Sum

Can you select elements that sum to exactly target?

hljs cpp

vector<bool> dp(target + 1, false);
dp[0] = true;

for (int x : a) {
    for (int s = target; s >= x; s--) {
        dp[s] = dp[s] || dp[s - x];
    }
}
bool possible = dp[target];

Count Subsets with Sum = Target

hljs cpp

vector<long long> dp(target + 1, 0);
dp[0] = 1;

for (int x : a) {
    for (int s = target; s >= x; s--) {
        dp[s] += dp[s - x];
    }
}
long long count = dp[target];

Minimum Number of Elements to Reach Target

hljs cpp

vector<int> dp(target + 1, INT_MAX);
dp[0] = 0;

for (int s = 1; s <= target; s++) {
    for (int x : a) {
        if (x <= s && dp[s - x] != INT_MAX) {
            dp[s] = min(dp[s], dp[s - x] + 1);
        }
    }
}
int answer = dp[target];  // INT_MAX if impossible

Coin Change

hljs cpp

// Minimum coins to make amount
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;

for (int coin : coins) {
    for (int s = coin; s <= amount; s++) {
        if (dp[s - coin] != INT_MAX) {
            dp[s] = min(dp[s], dp[s - coin] + 1);
        }
    }
}
int answer = dp[amount];

Bitmask DP

Use a bitmask to represent which elements have been used:

Travelling Salesman Problem (TSP)

hljs cpp

// dp[mask][i] = minimum cost to visit all cities in mask, ending at i
const int INF = 1e9;
int dp[1 << n][n];

memset(dp, INF, sizeof(dp));
dp[1][0] = 0;  // start at city 0

for (int mask = 1; mask < (1 << n); mask++) {
    for (int u = 0; u < n; u++) {
        if (!(mask & (1 << u))) continue;
        if (dp[mask][u] == INF) continue;
        for (int v = 0; v < n; v++) {
            if (mask & (1 << v)) continue;
            int newMask = mask | (1 << v);
            dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
        }
    }
}

int ans = INF;
for (int u = 0; u < n; u++) {
    ans = min(ans, dp[(1 << n) - 1][u] + dist[u][0]);
}

Assignment Problem

hljs cpp

// Assign n tasks to n workers, minimize total cost
// dp[mask] = minimum cost for the tasks in mask
vector<int> dp(1 << n, INF);
dp[0] = 0;

for (int mask = 0; mask < (1 << n); mask++) {
    int taskIndex = __builtin_popcount(mask);  // which task to assign next
    for (int worker = 0; worker < n; worker++) {
        int newMask = mask | (1 << worker);
        dp[newMask] = min(dp[newMask], dp[mask] + cost[taskIndex][worker]);
    }
}

Summary

0-1 knapsack: process items in reverse weight order (no reuse)
Unbounded knapsack: process items in forward weight order (unlimited reuse)
Subset sum: dp[s] = dp[s] || dp[s - x] for each element
Bitmask DP: O(2ⁿ × n) — use for n ≤ 20
All knapsack variants follow the same pattern: iterate items, iterate capacity

Ch 26: Dynamic Programming — Foundations Ch 28: Backtracking & Meet-in-the-Middle

Prefer reading offline? Download the full book as a PDF.

Download Free Book