SyntaxPilot
Courses/Competitive Programming/Lesson 33

Competitive Programming · Lesson 33 of 90 · 12 min

DP 2: knapsack variants

queued

These are the notes for Competitive Programming episode 33, part two of the dynamic programming section. Priya packs a trek backpack that can hold W kg; every item is either packed whole or left behind. An original problem, Trek Backpack, asks for the most valuable bag. Greedy by value per kg prints 30 instead of 48; trying all 2^n subsets is right but gets TLE at 40 items. The future only needs how many items we've decided on and how much weight we've used, so the state is dp[i][c], with two transitions: skip or take. One row is enough if c runs downwards; running it upwards lets an item be reused, which is exactly the unbounded knapsack. Replacing max with + gives the third variant: counting subsets with a given sum, mod 10^9 + 7. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Priya is going on a three-day trek with one backpack that holds 10 kg. Tent, stove, first-aid kit, power bank: each has a weight and a usefulness score. She can't pack half a tent. Which items make the most useful bag? The word knapsack is just an old word for backpack, and this exact situation (whole items, one weight limit) is the most famous DP family in contests.

Problem J · Trek Backpack

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

There are n items. Item i weighs wi kg and is worth vi. Choose some items, each at most once, with total weight at most W. Print the maximum total value.

  • Input: n and W (1 ≤ n ≤ 100, 1 ≤ W ≤ 10^5), then n lines wi vi (1 ≤ wi ≤ W, 0 ≤ vi ≤ 10^9).
  • Output: the maximum total value.
Input Output
3 10 / 6 30 / 5 24 / 5 24 48 (the two 5 kg items)
3 9 / 3 10 / 5 14 / 4 12 26 (5 kg + 4 kg)
3 7 / 3 4 / 4 5 / 2 3 9 (3 kg + 4 kg)
1 5 / 7 100 0 (nothing fits)

Attempt 1: greedy by value per kg (wrong)

Sort by vi / wi, best first (the comparator cross-multiplies, v[a] * w[b] > v[b] * w[a], so there is no floating-point division), and pack whatever still fits.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b) {    // best value per kg first
        return v[a] * w[b] > v[b] * w[a];
    });
    ll total = 0;
    int left = W;
    for (int i : id)
        if (w[i] <= left) { left -= w[i]; total += v[i]; }
    cout << total << "\n";
    return 0;
}

Sample 1 prints 30 (expected 48). The 6 kg item has the best ratio (5 per kg), greedy grabs it, and then neither 5 kg item fits in the 4 kg left. Value per kg is the correct greedy only for the fractional knapsack, where items can be cut (rice, sugar). With whole items, one choice can block better ones.

Attempt 2: all 2^n subsets (Time Limit Exceeded)

Bit i of the mask says whether item i is packed (episode 17).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    ll best = 0;
    for (ll m = 0; m < (1LL << n); m++) {     // bit i: take item i
        ll weight = 0, value = 0;
        for (int i = 0; i < n; i++)
            if (m >> i & 1) { weight += w[i]; value += v[i]; }
        if (weight <= W) best = max(best, value);
    }
    cout << best << "\n";
    return 0;
}

Samples: 48, 26, 9, all correct. With 40 items it prints Time Limit Exceeded: 2^40 ≈ 1.1 · 10^12 subsets, and n can be 100.

The key question: what does the future need to know?

Standing at item i, two bags that both weigh 7 kg are interchangeable: whatever is left, there are 3 kg of space either way. So the future only needs how many items have been decided and how much weight is used.

State: dp[i][c] = the best value using only the first i items, with total weight at most c.

Transitions for item i (weight wi, value vi):

Choice Value
skip item i dp[i−1][c]
take item i (if c ≥ wi) dp[i−1][c − wi] + vi

dp[i][c] = max of the two. Base: dp[0][c] = 0 for every c (no items, no value). Answer: dp[n][W]. There are (n + 1)(W + 1) ≈ 10^7 states, O(1) work each.

The table on sample 3

W = 7, items (3 kg, 4), (4 kg, 5), (2 kg, 3):

weight ≤ 0 1 2 3 4 5 6 7
no items 0 0 0 0 0 0 0 0
+ (3 kg, 4) 0 0 0 4 4 4 4 4
+ (4 kg, 5) 0 0 0 4 5 5 5 9
+ (2 kg, 3) 0 0 3 4 5 7 8 9

For example dp[2][7] = max(dp[1][7], dp[1][3] + 5) = max(4, 9) = 9, and dp[3][5] = max(dp[2][5], dp[2][3] + 3) = max(5, 7) = 7.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    // dp[i][c] = best value using the first i items, weight <= c
    vector<vector<ll>> dp(n + 1, vector<ll>(W + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int c = 0; c <= W; c++) {
            dp[i][c] = dp[i - 1][c];                          // skip item i
            if (c >= w[i - 1])
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // take it
        }
    cout << dp[n][W] << "\n";
    return 0;
}

Sample 1 prints 48. It works, but the full table at n = 100, W = 10^5 is 101 × 100001 long longs ≈ 80 MB.

One row is enough, if c runs downwards

Row i only reads row i − 1. Keep one row dp[c] and update it in place for each item:

dp[c] = max(dp[c], dp[c − wi] + vi)

The value read at dp[c − wi] must still be the old value (item i not used yet). If c runs from W down to wi, every smaller cell is still old when it is read. Memory drops from 80 MB to under 1 MB.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    vector<ll> dp(W + 1, 0);              // dp[c] = best value, weight <= c
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)   // DOWN: each item once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << "\n";
    return 0;
}
Input Output
sample 1 48
sample 2 26
sample 3 9
1 5 / 7 100 (too heavy) 0
the 40-item test that timed out 993 (instant)

The worst case, built inside main (n = 100, W = 10^5, item i weighs 1000 + 37i and is worth 10^9 − i):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 100, W = 100000;               // worst case, built here
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) { w[i] = 1000 + 37 * i; v[i] = 1000000000 - i; }
    vector<ll> dp(W + 1, 0);              // dp[c] = best value, weight <= c
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)   // DOWN: each item once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << "\n";
    return 0;
}

Output: 50999998725. Fifty-one items fit (1000·51 + 37·1275 = 98175 kg), worth almost 5.1 · 10^10, far past an int, and the 10^7-step loop runs in a blink.

A stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(vector<int>& w, vector<ll>& v, int W) {
    int n = w.size();
    ll best = 0;
    for (int m = 0; m < (1 << n); m++) {
        ll wt = 0, val = 0;
        for (int i = 0; i < n; i++) if (m >> i & 1) { wt += w[i]; val += v[i]; }
        if (wt <= W) best = max(best, val);
    }
    return best;
}
ll fast(vector<int>& w, vector<ll>& v, int W) {
    vector<ll> dp(W + 1, 0);
    for (int i = 0; i < (int)w.size(); i++)
        for (int c = W; c >= w[i]; c--) dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    return dp[W];
}
int main() {
    mt19937 rng(33);
    for (int t = 1; t <= 1000; t++) {
        int n = rng() % 12 + 1, W = rng() % 50 + 1;
        vector<int> w(n);
        vector<ll> v(n);
        for (int i = 0; i < n; i++) { w[i] = rng() % 20 + 1; v[i] = rng() % 100; }
        if (brute(w, v, W) != fast(w, v, W)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed.

Variant 2: the unbounded knapsack

Write the one-row loop with c going up and run sample 2:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    vector<ll> dp(W + 1, 0);              // dp[c] = best value, weight <= c
    for (int i = 0; i < n; i++)
        for (int c = w[i]; c <= W; c++)   // up?
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << "\n";
    return 0;
}

Output: 30 (expected 26): three copies of the 3 kg item worth 10. Going up, dp[c − wi] has already been updated for this same item, so the item is packed again and again.

That "bug" is the correct answer to a different problem: unlimited copies of each item (coins of each value, bricks, packets). This is called the unbounded knapsack.

Loop direction Meaning
c from W down to wi each item at most once (0/1 knapsack)
c from wi up to W unlimited copies (unbounded knapsack)

Same state, same transition; only the order of one loop changes the meaning.

Variant 3: counting ways (mod 10^9 + 7)

n coins, each used at most once. How many subsets sum to exactly S? Coins 1 2 3 4 and S = 5: {1, 4} and {2, 3}, so 2.

  • max(skip, take) becomes skip + take.
  • Base: ways[0] = 1 (the empty subset).
  • Counts explode (100 coins of value 1, S = 50: C(100, 50) ≈ 10^29), so print them mod 10^9 + 7 (episode 21).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;

int main() {
    int n, S;
    cin >> n >> S;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    vector<ll> ways(S + 1, 0);             // ways[s] = subsets with sum s
    ways[0] = 1;                           // the empty subset
    for (int x : a)
        for (int s = S; s >= x; s--)       // down: each coin once
            ways[s] = (ways[s] + ways[s - x]) % MOD;   // skip + take
    cout << ways[S] << "\n";
    return 0;
}
Input Output
4 5 / 1 2 3 4 2
100 coins of value 1, S = 50 538992043 (= C(100, 50) mod 10^9 + 7)

Complexity vs the constraints

Approach Time Memory Verdict
all subsets O(2^n · n) O(n) TLE at n = 40
greedy by ratio O(n log n) O(n) wrong (30 vs 48)
dp[i][c] table O(n · W) ≈ 10^7 O(n · W) ≈ 80 MB accepted, but heavy
one row, c down O(n · W) ≈ 10^7 O(W) < 1 MB accepted

Common mistakes (and the real outputs)

Bug 1: the upward loop in a 0/1 knapsack

Shown above: sample 2 prints 30 instead of 26 because an item is reused. In a 0/1 knapsack, c must go down.

Bug 2: "exactly c" read as "at most c"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    vector<ll> dp(W + 1, LLONG_MIN / 2);  // weight exactly c?
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)   // DOWN: each item once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << "\n";
    return 0;
}

On the too-heavy edge case it prints -4611686018427387904. With every cell except dp[0] set to −∞, dp[c] means "weight exactly c"; no subset weighs exactly 5, so the cell is still −∞. Either start every cell at 0 (meaning "at most c"), or keep exact weights and print the max over all c.

Summary table

Mistake What you see Why Fix
greedy by value per kg 30 instead of 48 whole items can't be split DP over (i, c)
for (c = w[i]; c <= W; c++) in 0/1 30 instead of 26 the item is reused c from W down to wi
dp(W + 1, LLONG_MIN / 2), print dp[W] -4611686018427387904 weight exactly W unreachable start at 0, or max over c
full 2D table at tight memory limits 80 MB, may get MLE keeps every row one row
int values overflow past 2.1 · 10^9 the sum of values is up to 10^11 long long

Mini project

Write a "packing assistant": read items and a capacity, solve the 0/1 knapsack with the one-row DP, then reconstruct the chosen items (keep the full 2D table, or a bool take[i][c] table, and walk back from dp[n][W]: if dp[i][c] ≠ dp[i−1][c], item i was taken, so c −= wi). Print the packed items and their total weight. Add a flag that switches to unlimited copies (the upward loop), and compare both answers on the samples.

Practice

  1. Capacity up to 10^9, but every value is at most 1000 (n ≤ 100).

    Answer n · W is now 10^11: too big. Swap the roles: minW[x] = the smallest weight that reaches total value exactly x (x ≤ 100 · 1000 = 10^5), with minW[0] = 0, others +∞, and the same downward loop over x. The answer is the largest x with minW[x] ≤ W. O(n · Σv) = 10^7. On sample 1 it also prints <b>48</b>.

  2. Print which items to pack for sample 1.

    Answer Walk back from dp[3][10] = 48: item 3 was taken (dp[3][10] ≠ dp[2][10]), then item 2. Items <b>2 and 3</b>, 10 kg, value 48.

  3. Count the ordered ways to pay S with unlimited coins (order matters: 2+3 and 3+2 are different).

    Answer Put the sum loop outside and the coin loop inside: for s = 1 … S, for each coin c ≤ s, ways[s] += ways[s − c]. Coins {2, 3}, S = 7: <b>3</b> ordered ways (2+2+3, 2+3+2, 3+2+2), but only <b>1</b> unordered way (coins outside, s going up).

  4. Two backpacks, capacities A and B, each item in at most one bag.

    Answer State dp[a][b] = best value with a kg used in bag 1 and b kg in bag 2; for each item, loop a and b downwards and try: skip, put in bag 1, put in bag 2. O(n · A · B). Sample 1 items with A = 5, B = 6: <b>54</b> (a 5 kg item in bag 1, the 6 kg item in bag 2).

Quick quiz

Coins of value 2 and 3, unlimited. To count the ways to make S (order not counted), with the coin loop outside, which way should s go?

A) s from S down to x · B) s from x up to S · C) either works · D) neither works

Answer

B. Going up lets ways[s − x] already include coin x, so the same coin can be used again, which is what "unlimited" means.

Interview questions

  1. 0/1 vs unbounded vs fractional knapsack? 0/1: each item once (DP, c down). Unbounded: unlimited copies (DP, c up). Fractional: items can be cut (greedy by value per weight is optimal).
  2. Why is the 0/1 knapsack O(n · W) not polynomial? W is a number in the input, written in about log W bits, so O(n · W) is exponential in the input size. It's called pseudo-polynomial.
  3. How do you save memory in a knapsack DP? Each row only reads the previous row, so keep one row and choose the loop direction carefully.
  4. How do you reconstruct the chosen items? Keep the full table (or a choice table) and walk back from dp[n][W].
  5. What changes when you count instead of optimise? max becomes +, the base becomes ways[0] = 1, and you work modulo a prime.
  6. When would you index the DP by value instead of weight? When W is huge but the total value is small.

Glossary

Term Meaning Example
Knapsack Choose items under a capacity to maximise value Trek Backpack
0/1 knapsack Each item taken at most once c loop goes down
Unbounded knapsack Unlimited copies of each item c loop goes up
Fractional knapsack Items can be cut; greedy by ratio works rice, sugar
State What the future needs to know (items decided i, capacity c)
Transition How a state is built from others skip / take
Base case The starting values dp[0][c] = 0, ways[0] = 1
Rolling array (one row) Reusing one row instead of a full table vector<ll> dp(W + 1)
Pseudo-polynomial Polynomial in the value W, not in its digit count O(n · W)
Subset sum count Number of subsets with a given sum coins 1 2 3 4, S = 5 → 2
Modulo 10^9 + 7 Keeping huge counts small with a prime 538992043
Greedy Take the locally best choice best value per kg first
Stress test Fast vs brute force on random small tests all 1000 tests passed
−∞ sentinel A value meaning "impossible" LLONG_MIN / 2

Summary

  • Whole items break greedy by ratio (30 vs 48); all 2^n subsets TLE at n = 40.
  • State dp[i][c]: items decided, capacity used. Transitions: skip or take. Base: 0. Answer: dp[n][W]. O(n · W).
  • One row: c down = each item once (0/1); c up = unlimited copies (unbounded).
  • Counting: max → +, ways[0] = 1, mod 10^9 + 7.
  • Real bugs: the upward loop (30 vs 26), the exact-weight trap (-4611686018427387904).

Solutions in C++, Java and Python

Problem J · Trek Backpack

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, W;
    cin >> n >> W;
    vector<int> w(n);
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
    vector<ll> dp(W + 1, 0);              // dp[c] = best value, weight <= c
    for (int i = 0; i < n; i++)
        for (int c = W; c >= w[i]; c--)   // DOWN: each item once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    cout << dp[W] << "\n";
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int W = (int) in.nval;
        long[] dp = new long[W + 1];                 // dp[c] = best value, weight <= c
        for (int i = 0; i < n; i++) {
            in.nextToken(); int w = (int) in.nval;
            in.nextToken(); long v = (long) in.nval;
            for (int c = W; c >= w; c--)             // down: each item once
                dp[c] = Math.max(dp[c], dp[c - w] + v);
        }
        System.out.println(dp[W]);
    }
}

Python (fine for the samples; for n · W = 10^7 in Python, use NumPy or C++)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, W = int(data[0]), int(data[1])
    dp = [0] * (W + 1)                     # dp[c] = best value, weight <= c
    for i in range(n):
        w, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
        for c in range(W, w - 1, -1):      # down: each item once
            if dp[c - w] + v > dp[c]:
                dp[c] = dp[c - w] + v
    print(dp[W])

main()

Next episode: DP 3: DP on subsequences and strings (LCS and edit distance).