What signals in a problem statement indicate the 0/1 knapsack sub-pattern?

"each item can be used once"; "capacity W", "weight and value"; "is there a subset with sum S"; two limits at once (zeros ≤ m and ones ≤ n)

0/1 knapsack (DP — Knapsack Sub-pattern)

Q: What makes 0/1 knapsack different from other sub-patterns?

The **backwards** capacity loop is what keeps each item single-use. With two limits the table becomes 2D and **both** loops go backwards.

Each item is taken at most once. dp[c] = max(dp[c], dp[c − w] + v) with c from high to low.

Signals in the problem statement

›
"each item can be used once"
›
"capacity W", "weight and value"
›
"is there a subset with sum S"
›
two limits at once (zeros ≤ m and ones ≤ n)

What makes it different

The backwards capacity loop is what keeps each item single-use. With two limits the table becomes 2D and both loops go backwards.

Questions

ordered from “learn the idea” to “recognise it without help”

1
0/1 Knapsack
Basic Anchor·GeeksforGeeks
WalkthroughMedium
2
Subset Sum Problem
Basic Reinforcement·GeeksforGeeks
WalkthroughMedium
3
Ones and Zeroes
Pattern Transfer·LeetCode #474
WalkthroughMedium

Template

zero-one-template.cpp

// 0/1 knapsack in one row: dp[c] = best value with capacity c.
// c goes HIGH -> LOW so dp[c - w] still belongs to the previous items (each item once).
int knapsack01(int W, const vector<int>& wt, const vector<int>& val) {
    vector<int> dp(W + 1, 0);
    for (size_t i = 0; i < wt.size(); i++)
        for (int c = W; c >= wt[i]; c--)
            dp[c] = max(dp[c], dp[c - wt[i]] + val[i]);   // skip vs take
    return dp[W];
}

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

DP — Knapsack overview Count ways