LeetCode Patterns - 13 DP - Knapsack

Post by ailswan June. 02, 2026

中文 ↓
LeetCode Patterns  · 

🎯 DP - Knapsack

1️⃣ Core Framework

When discussing Knapsack DP, I frame it as:

  1. What problem pattern knapsack solves
  2. 0/1 knapsack
  3. Complete knapsack
  4. State definition
  5. Recurrence relation
  6. Iteration order
  7. Space optimization
  8. Common LeetCode variations
  9. Common edge cases
  10. Senior-level explanation

2️⃣ What Problem Are We Solving?

Knapsack DP is used when we need to choose items under a constraint.

It is commonly used for:

The core idea is:

For each item,
decide whether to take it or skip it,
while respecting a capacity constraint.

👉 Interview Answer

Knapsack DP is used for problems where we choose items under a capacity or resource constraint.

The most common decision is whether to take or skip an item.

The key is to define what the capacity means, whether each item can be used once or multiple times, and what the DP state represents.

3️⃣ What Is 0/1 Knapsack?

Problem

Given items with weights and values, choose a subset of items to maximize total value without exceeding capacity.

Each item can be used at most once.

Example

weights = [1, 3, 4]
values  = [15, 20, 30]
capacity = 4

Possible choices:

item 0 + item 1:
weight = 1 + 3 = 4
value = 15 + 20 = 35

item 2:
weight = 4
value = 30

Best answer:

35

Why 0/1?

Each item has two choices:

0 = do not take
1 = take

So it is called 0/1 knapsack.

👉 Interview Answer

In 0/1 knapsack, each item can be used at most once.

For every item, we decide whether to skip it or take it.

If we take it, we consume capacity and gain value.

The goal is usually to maximize value or determine whether a target capacity can be formed.

4️⃣ 0/1 Knapsack State Definition

2D State

A classic state is:

dp[i][c] = maximum value using the first i items with capacity c

Where:

i = number of items considered
c = current capacity

Meaning

dp[i][c]

means:

Given only items from index 0 to i - 1,
what is the best value we can achieve with capacity c?

Why Use First i Items?

Using first i items makes the transition clean:

current item = item i - 1
previous state = first i - 1 items

👉 Interview Answer

For 0/1 knapsack, I often define dp[i][c] as the best value using the first i items with capacity c.

The item currently being considered is item i - 1.

This state cleanly separates the current item from the previous subproblem.

5️⃣ 0/1 Knapsack Recurrence

Decision

For item i - 1, we have two choices.

Choice 1: Skip the item

dp[i - 1][c]

Choice 2: Take the item

Only possible if:

c >= weight[i - 1]

Then value is:

dp[i - 1][c - weight[i - 1]] + value[i - 1]

Recurrence

dp[i][c] = max(
    dp[i - 1][c],
    dp[i - 1][c - weight[i - 1]] + value[i - 1]
)

If capacity is not enough:

dp[i][c] = dp[i - 1][c]

👉 Interview Answer

The recurrence comes from the take-or-skip decision.

If I skip the current item, the answer stays dp[i - 1][c].

If I take the current item, I gain its value and use remaining capacity c - weight.

Since each item can be used only once, the take transition comes from the previous item row.

6️⃣ 0/1 Knapsack 2D Code

Code

def knapsack_01(weights, values, capacity):
    n = len(weights)

    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for c in range(capacity + 1):
            # skip item
            dp[i][c] = dp[i - 1][c]

            # take item
            if c >= weight:
                dp[i][c] = max(
                    dp[i][c],
                    dp[i - 1][c - weight] + value
                )

    return dp[n][capacity]

Complexity

Time: O(n * capacity)
Space: O(n * capacity)

👉 Interview Answer

The 2D version is the most intuitive.

Rows represent how many items have been considered.

Columns represent capacity.

For each item and capacity, I compute the best answer by either skipping or taking the item.

7️⃣ Space Optimization for 0/1 Knapsack

Observation

In the 2D recurrence:

dp[i][c]

only depends on:

dp[i - 1][c]
dp[i - 1][c - weight]

So we can compress rows into one 1D array.

1D State

dp[c] = best value achievable with capacity c after processing some items

Critical Detail

For 0/1 knapsack, capacity must iterate backward:

for c from capacity down to weight

Why Backward?

Backward iteration prevents using the same item more than once.

👉 Interview Answer

0/1 knapsack can be optimized from 2D to 1D because each row only depends on the previous row.

The important detail is iterating capacity backward.

Backward iteration ensures the current item is used at most once.

8️⃣ 0/1 Knapsack 1D Code

Code

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)

    dp = [0] * (capacity + 1)

    for i in range(n):
        weight = weights[i]
        value = values[i]

        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Complexity

Time: O(n * capacity)
Space: O(capacity)

Key Rule

0/1 knapsack → iterate capacity backward

👉 Interview Answer

In the optimized version, dp[c] stores the best value for capacity c.

For each item, I iterate capacity backward.

This guarantees dp[c - weight] still comes from the previous item state, so the current item cannot be reused.

9️⃣ Complete Knapsack

What Is Complete Knapsack?

In complete knapsack, each item can be used unlimited times.

Examples:

Coin Change
Coin Change II
Unbounded Knapsack

Difference From 0/1 Knapsack

0/1 knapsack:

each item can be used once

Complete knapsack:

each item can be used multiple times

Iteration Direction

For complete knapsack, capacity usually iterates forward:

for c from weight to capacity

👉 Interview Answer

Complete knapsack allows each item to be used multiple times.

That changes the iteration order.

In 1D DP, we iterate capacity forward so the current item can contribute to later states in the same item iteration.

🔟 Complete Knapsack Code

Maximum Value Version

def complete_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(weight, capacity + 1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Key Rule

complete knapsack → iterate capacity forward

Why Forward?

Forward iteration allows:

dp[c - weight]

to already include the current item.

That makes repeated use possible.

👉 Interview Answer

In complete knapsack, forward capacity iteration allows the same item to be reused.

When computing dp[c], dp[c - weight] may already include the current item from this same iteration.

That is exactly what we want for unlimited usage.

1️⃣1️⃣ 0/1 vs Complete Knapsack

Main Difference

Pattern Item Usage Capacity Iteration
0/1 Knapsack Use each item once Backward
Complete Knapsack Use each item unlimited times Forward

Why This Matters

Same recurrence shape:

dp[c] = best(dp[c], dp[c - weight] + value)

But different iteration order changes whether the current item can be reused.

👉 Interview Answer

The main difference between 0/1 and complete knapsack is whether each item can be reused.

In 0/1 knapsack, I iterate capacity backward to prevent reusing the current item.

In complete knapsack, I iterate capacity forward to allow reusing the current item.

1️⃣2️⃣ Subset Sum

Problem

Given nums and target, determine whether some subset sums to target.

Each number can be used once.

State Definition

dp[s] = whether sum s can be formed

Code

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

Why This Is 0/1 Knapsack

Each number can be used once.

So iterate sum backward.

👉 Interview Answer

Subset Sum is a 0/1 knapsack problem.

Each number can either be selected or skipped.

I define dp[s] as whether sum s can be formed.

Since each number can be used once, I iterate the sum backward.

1️⃣3️⃣ Partition Equal Subset Sum

Problem

Given nums, determine whether nums can be partitioned into two subsets with equal sum.

Key Insight

If total sum is odd:

impossible

If total sum is even, we need to find a subset with sum:

total // 2

Code

def can_partition(nums):
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

👉 Interview Answer

Partition Equal Subset Sum reduces to subset sum.

If the total sum is odd, equal partition is impossible.

Otherwise, we need to determine whether some subset sums to total / 2.

Since each number can be used once, this is 0/1 knapsack.

1️⃣4️⃣ Last Stone Weight II

Problem

Given stones, smash stones so the final remaining weight is minimized.

Key Insight

This is equivalent to partitioning stones into two groups whose sum difference is minimized.

Let total sum be:

total

If one group has sum:

s

Then the other group has:

total - s

Difference:

total - 2s

We want s as large as possible but not greater than:

total // 2

Code

def last_stone_weight_ii(stones):
    total = sum(stones)
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for stone in stones:
        for s in range(target, stone - 1, -1):
            dp[s] = dp[s] or dp[s - stone]

    for s in range(target, -1, -1):
        if dp[s]:
            return total - 2 * s

    return 0

👉 Interview Answer

Last Stone Weight II can be transformed into a partition problem.

We want to split stones into two groups with the smallest possible difference.

So we find the largest subset sum not exceeding total / 2.

This is a 0/1 knapsack subset-sum problem.

1️⃣5️⃣ Target Sum

Problem

Given nums and target, assign + or - signs to each number so the expression equals target.

Transformation

Let:

P = sum of numbers with plus sign
N = sum of numbers with minus sign

We need:

P - N = target
P + N = total

Add both equations:

2P = target + total
P = (target + total) / 2

So the problem becomes:

count subsets with sum P

Code

def find_target_sum_ways(nums, target):
    total = sum(nums)

    if abs(target) > total:
        return 0

    if (target + total) % 2 == 1:
        return 0

    subset_sum = (target + total) // 2

    dp = [0] * (subset_sum + 1)
    dp[0] = 1

    for num in nums:
        for s in range(subset_sum, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[subset_sum]

Why Backward?

Each number can be assigned once.

So this is 0/1 counting knapsack.

👉 Interview Answer

Target Sum can be transformed into a subset-sum counting problem.

If P is the sum of numbers assigned plus, and N is the sum assigned minus, then P - N equals target and P + N equals total.

This gives P = (target + total) / 2.

Then we count how many subsets sum to P.

1️⃣6️⃣ Coin Change

Problem

Given coins and amount, return the minimum number of coins needed to make the amount.

Coins can be used unlimited times.

State Definition

dp[x] = minimum coins needed to make amount x

Code

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

Why Complete Knapsack?

Each coin can be used unlimited times.

So amount iterates forward.

👉 Interview Answer

Coin Change is a complete knapsack problem.

Each coin can be used multiple times.

I define dp[x] as the minimum number of coins needed for amount x.

Since coins are reusable, I iterate amount forward for each coin.

1️⃣7️⃣ Coin Change II

Problem

Given coins and amount, return the number of combinations that make up the amount.

Order does not matter.

Example:

amount = 5
coins = [1, 2, 5]

combinations:
5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

answer = 4

Code

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]

    return dp[amount]

Important Loop Order

For combinations where order does not matter:

coins outer loop
amount inner loop

👉 Interview Answer

Coin Change II counts combinations, not permutations.

I put coins in the outer loop and amount in the inner loop.

This ensures each combination is counted once in coin order.

Since coins can be reused, amount iterates forward.

1️⃣8️⃣ Combination Sum IV

Problem

Given nums and target, return the number of possible ordered combinations that sum to target.

Order matters.

Example:

nums = [1, 2, 3]
target = 4

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1

answer = 7

Code

def combination_sum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for total in range(1, target + 1):
        for num in nums:
            if total >= num:
                dp[total] += dp[total - num]

    return dp[target]

Important Loop Order

For permutations where order matters:

amount outer loop
nums inner loop

👉 Interview Answer

Combination Sum IV counts ordered combinations.

Because order matters, I iterate total first and then try every number as the last element.

This allows different orders to be counted separately.

1️⃣9️⃣ Ones and Zeroes

Problem

Given binary strings and two limits:

m = number of zeros allowed
n = number of ones allowed

Find the maximum number of strings we can choose.

Each string can be used once.

State Definition

dp[z][o] = max number of strings using at most z zeros and o ones

Code

def find_max_form(strs, m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count("0")
        ones = s.count("1")

        for z in range(m, zeros - 1, -1):
            for o in range(n, ones - 1, -1):
                dp[z][o] = max(
                    dp[z][o],
                    dp[z - zeros][o - ones] + 1
                )

    return dp[m][n]

Why Backward?

Each string can be used once.

This is 0/1 knapsack with two capacities.

👉 Interview Answer

Ones and Zeroes is a 0/1 knapsack problem with two capacity dimensions.

The capacities are zeros and ones.

Each string can be selected once, so both dimensions iterate backward.

The DP value is the maximum number of strings selected.

2️⃣0️⃣ 0/1 Knapsack Counting Variation

Pattern

Sometimes we are not maximizing value.

Instead, we count how many ways to reach a target.

State:

dp[s] = number of ways to form sum s

Transition:

dp[s] += dp[s - num]

For 0/1 counting:

iterate s backward

Example

Target Sum uses this pattern.

for num in nums:
    for s in range(target, num - 1, -1):
        dp[s] += dp[s - num]

👉 Interview Answer

Knapsack is not only about maximizing value.

It can also count the number of ways to form a target.

If each item can be used once, I iterate capacity backward.

The transition adds the number of ways from the previous capacity state.

2️⃣1️⃣ Max Value vs Count Ways vs Feasibility

Three Common DP Meanings

1. Feasibility

dp[s] = can we form sum s?

Transition:

dp[s] = dp[s] or dp[s - num]

2. Count Ways

dp[s] = number of ways to form sum s

Transition:

dp[s] += dp[s - num]

3. Max / Min Value

dp[c] = best value under capacity c

Transition:

dp[c] = max(dp[c], dp[c - weight] + value)

or:

dp[c] = min(dp[c], dp[c - coin] + 1)

👉 Interview Answer

Knapsack DP can represent different meanings.

Sometimes dp means whether a sum is possible.

Sometimes dp means how many ways exist.

Sometimes dp means the best value or minimum cost.

The recurrence depends on what the state represents.

2️⃣2️⃣ Loop Order Summary

0/1 Knapsack

Each item used once:

for item in items:
    for capacity in range(C, weight - 1, -1):
        update

Complete Knapsack

Each item used unlimited times:

for item in items:
    for capacity in range(weight, C + 1):
        update

Combination Counting

Order does not matter:

for coin in coins:
    for amount in range(coin, target + 1):
        update

Permutation Counting

Order matters:

for amount in range(1, target + 1):
    for num in nums:
        update

👉 Interview Answer

Loop order is one of the most important parts of knapsack DP.

For 0/1 knapsack, capacity goes backward.

For complete knapsack, capacity goes forward.

For counting combinations, items go outside.

For counting ordered permutations, target amount goes outside.

2️⃣3️⃣ Common Edge Cases

Capacity Is Zero

capacity = 0

Usually:

dp[0] = 0

for min or max value,

or:

dp[0] = True

for feasibility,

or:

dp[0] = 1

for counting ways.

Empty Items

weights = []
nums = []
coins = []

Need return based on target.

Target Impossible

Use:

False
-1
0

depending on the problem.

Odd Total Sum

For partition problems:

if total is odd, return False

Zero Values

Zeros can affect counting problems.

For example, Target Sum with zeros can multiply the number of ways.

👉 Interview Answer

Common knapsack edge cases include zero capacity, empty item list, impossible target, odd total sum in partition problems, and zero values in counting problems.

I pay special attention to dp[0], because it often defines the base meaning of the entire DP.

2️⃣4️⃣ Common Mistakes

Mistake 1: Wrong Iteration Direction

Using forward iteration for 0/1 knapsack accidentally reuses items.

Mistake 2: Wrong Loop Order for Counting

Coin Change II and Combination Sum IV have different loop orders.

Mistake 3: Incorrect Base Case

For counting ways:

dp[0] = 1

For feasibility:

dp[0] = True

For min coins:

dp[0] = 0

Mistake 4: Confusing Capacity With Index

Capacity is the resource limit.

Index is the item position.

They are different dimensions.

Mistake 5: Optimizing Space Too Early

Understand 2D recurrence first, then optimize to 1D.

👉 Interview Answer

Common knapsack mistakes include wrong capacity iteration direction, wrong loop order for counting problems, incorrect dp[0] base case, confusing item index with capacity, and optimizing space before understanding the recurrence.

I avoid these by first identifying whether the problem is 0/1, complete, feasibility, counting, or optimization.

2️⃣5️⃣ When Knapsack DP Applies

Good Fit

Use knapsack DP when the problem involves:

choose or skip items
capacity constraint
target sum
subset sum
count ways to form target
maximize value under limit
minimize cost under limit
each item used once or unlimited times

Problem Signals

Look for words like:

subset
partition
target sum
capacity
coins
ways to make amount
use each item once
unlimited use
maximum value
minimum number

👉 Interview Answer

I consider knapsack DP when the problem involves choosing items under a capacity or target constraint.

The first question I ask is whether each item can be used once or unlimited times.

Then I ask whether the goal is feasibility, counting, maximizing, or minimizing.

2️⃣6️⃣ When Knapsack DP Does Not Apply

Not Good Fit

Knapsack DP may not be ideal when:

there is no capacity or target dimension
choices are not reusable subproblems
input size makes capacity too large
problem is shortest path
problem requires all actual solutions

Better Alternatives

Problem Type Better Pattern
Generate all subsets Backtracking
Shortest path BFS / Dijkstra
Large numeric capacity Greedy / Math / Approximation
Connectivity DFS / Union Find
Range queries Prefix Sum / Segment Tree

👉 Interview Answer

Knapsack DP is not always suitable.

If there is no capacity or target dimension, it may not be a knapsack problem.

If capacity is extremely large, pseudo-polynomial DP may be too expensive.

If the problem asks to list all solutions, backtracking may be more appropriate.

2️⃣7️⃣ Standard Templates

0/1 Knapsack Max Value Template

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Complete Knapsack Max Value Template

def complete_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(weight, capacity + 1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

0/1 Feasibility Template

def can_form_target(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

0/1 Counting Template

def count_subsets(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[target]

Complete Knapsack Min Coins Template

def min_coins(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

Complete Knapsack Count Combinations Template

def count_combinations(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]

    return dp[amount]

Ordered Permutation Count Template

def count_ordered(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for total in range(1, target + 1):
        for num in nums:
            if total >= num:
                dp[total] += dp[total - num]

    return dp[target]

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Knapsack DP is a family of dynamic programming problems where we choose items under a capacity or target constraint.

The most important questions are: what is the capacity, what does each item represent, can each item be used once or multiple times, and is the goal feasibility, counting, maximization, or minimization.

In 0/1 knapsack, each item can be used at most once. The classic state is dp[i][c], meaning the best value using the first i items with capacity c.

For each item, we either skip it or take it. If we skip it, the value is dp[i - 1][c]. If we take it, the value is dp[i - 1][c - weight] plus the current item value.

The 2D version is easiest to understand. Then we can optimize to 1D because each row only depends on the previous row.

In 1D 0/1 knapsack, capacity must iterate backward. This prevents the current item from being reused within the same iteration.

In complete knapsack, each item can be used unlimited times. Therefore, capacity iterates forward. This allows dp[c - weight] to already include the current item, which enables reuse.

Many LeetCode problems are knapsack variations. Partition Equal Subset Sum is subset-sum feasibility. Target Sum is subset-sum counting after algebraic transformation. Coin Change is complete knapsack minimizing number of coins. Coin Change II counts combinations. Combination Sum IV counts ordered combinations, so the loop order changes.

A key senior-level point is that the meaning of dp determines the transition. If dp means feasibility, we use boolean OR. If dp means count, we add ways. If dp means max value, we take max. If dp means min cost, we take min.

Loop order is also critical. For 0/1 usage, iterate capacity backward. For unlimited usage, iterate capacity forward. For combination counting, iterate items outside. For ordered permutation counting, iterate target amount outside.

The complexity is usually O(number of items × capacity). This is pseudo-polynomial because it depends on the numeric capacity, not just input length.

At a senior level, I would explain: what the item is, what the capacity is, whether item usage is once or unlimited, what dp[c] represents, why the iteration direction is correct, and whether the problem is feasibility, counting, max value, or min cost.

⭐ Final Insight

Knapsack DP 的核心不是“背 0/1 背包模板”。

它的核心是 choose items under constraints。

Senior-level 的重点是：

item 是什么， capacity 是什么， 每个 item 能不能重复使用， dp 表示 feasibility、count、max value 还是 min cost， loop direction 为什么是 backward 或 forward， 以及 loop order 是否会影响组合和排列的计数。

能讲清楚这些， Knapsack 就不是一个单独题型， 而是一整类 target、capacity、subset、coin change 问题的 DP 建模方法。

中文部分

🎯 DP - Knapsack

1️⃣ 核心框架

讨论 Knapsack DP 时，我通常从：

  1. Knapsack 解决什么问题
  2. 0/1 knapsack
  3. Complete knapsack
  4. State definition
  5. Recurrence relation
  6. Iteration order
  7. Space optimization
  8. 常见 LeetCode 变体
  9. 常见 edge cases
  10. 高级工程师解释方式

2️⃣ 要解决什么问题？

Knapsack DP 用于在 constraint 下选择 items。

它常用于：

核心思想是：

对每个 item，
决定 take 还是 skip，
同时不能超过 capacity constraint。

👉 面试回答

Knapsack DP 用于在 capacity 或 resource constraint 下选择 items。

最常见 decision 是 take or skip。

关键是定义 capacity 表示什么， 每个 item 能用一次还是多次， 以及 DP state 表示什么。

3️⃣ 什么是 0/1 Knapsack？

Problem

给定 items， 每个 item 有 weight 和 value。

选择一些 items， 在不超过 capacity 的情况下 maximize total value。

每个 item 最多只能使用一次。

Example

weights = [1, 3, 4]
values  = [15, 20, 30]
capacity = 4

Possible choices:

item 0 + item 1:
weight = 1 + 3 = 4
value = 15 + 20 = 35

item 2:
weight = 4
value = 30

Best answer:

35

为什么叫 0/1？

每个 item 只有两个选择：

0 = do not take
1 = take

所以叫 0/1 knapsack。

👉 面试回答

在 0/1 knapsack 中， 每个 item 最多使用一次。

对每个 item， 我们决定 skip 它还是 take 它。

如果 take，就消耗 capacity 并获得 value。

目标通常是 maximize value， 或者判断能否形成某个 target capacity。

4️⃣ 0/1 Knapsack State Definition

2D State

经典 state 是：

dp[i][c] = 使用前 i 个 items，在 capacity c 下的最大 value

其中：

i = 已经考虑的 item 数量
c = 当前 capacity

Meaning

dp[i][c]

表示：

只使用 index 0 到 i - 1 的 items，
在 capacity c 下能得到的最大 value。

为什么用 First i Items？

因为这样 transition 清楚：

current item = item i - 1
previous state = first i - 1 items

👉 面试回答

对 0/1 knapsack， 我通常定义 dp[i][c] 为使用前 i 个 items， capacity 为 c 时的最大 value。

当前考虑的 item 是 i - 1。

这个 state 可以清楚地区分当前 item 和 previous subproblem。

5️⃣ 0/1 Knapsack Recurrence

Decision

对于 item i - 1，有两个选择。

Choice 1: Skip

dp[i - 1][c]

Choice 2: Take

只有当：

c >= weight[i - 1]

才可以 take。

Value 是：

dp[i - 1][c - weight[i - 1]] + value[i - 1]

Recurrence

dp[i][c] = max(
    dp[i - 1][c],
    dp[i - 1][c - weight[i - 1]] + value[i - 1]
)

如果 capacity 不够：

dp[i][c] = dp[i - 1][c]

👉 面试回答

Recurrence 来自 take-or-skip decision。

如果 skip 当前 item， 答案是 dp[i - 1][c]。

如果 take 当前 item， 就获得当前 value， 并消耗 weight， 剩余 capacity 是 c - weight。

因为每个 item 只能使用一次， 所以 take transition 必须来自 previous item row。

6️⃣ 0/1 Knapsack 2D Code

Code

def knapsack_01(weights, values, capacity):
    n = len(weights)

    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for c in range(capacity + 1):
            dp[i][c] = dp[i - 1][c]

            if c >= weight:
                dp[i][c] = max(
                    dp[i][c],
                    dp[i - 1][c - weight] + value
                )

    return dp[n][capacity]

Complexity

Time: O(n * capacity)
Space: O(n * capacity)

👉 面试回答

2D 版本是最直观的。

Row 表示已经考虑了多少 items。

Column 表示 capacity。

对每个 item 和 capacity， 我通过 skip 或 take 来计算最优答案。

7️⃣ 0/1 Knapsack Space Optimization

Observation

2D recurrence 中：

dp[i][c]

只依赖：

dp[i - 1][c]
dp[i - 1][c - weight]

所以可以压缩成 1D array。

1D State

dp[c] = 处理到当前 items 后，capacity c 能得到的 best value

Critical Detail

对于 0/1 knapsack，capacity 必须倒序遍历：

for c from capacity down to weight

为什么要倒序？

倒序可以防止同一个 item 在同一轮被重复使用。

👉 面试回答

0/1 knapsack 可以从 2D 优化成 1D， 因为每一行只依赖上一行。

关键细节是 capacity 要倒序遍历。

倒序可以保证当前 item 最多被使用一次。

8️⃣ 0/1 Knapsack 1D Code

Code

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)

    dp = [0] * (capacity + 1)

    for i in range(n):
        weight = weights[i]
        value = values[i]

        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Complexity

Time: O(n * capacity)
Space: O(capacity)

Key Rule

0/1 knapsack → capacity backward

👉 面试回答

在优化版本中， dp[c] 表示 capacity c 下的 best value。

对每个 item， 我倒序遍历 capacity。

这样 dp[c - weight] 仍然来自 previous item state， 所以当前 item 不会被重复使用。

9️⃣ Complete Knapsack

什么是 Complete Knapsack？

Complete knapsack 中，每个 item 可以使用无限次。

Examples:

Coin Change
Coin Change II
Unbounded Knapsack

和 0/1 Knapsack 的区别

0/1 knapsack：

each item can be used once

Complete knapsack：

each item can be used multiple times

Iteration Direction

Complete knapsack 中，capacity 通常正序遍历：

for c from weight to capacity

👉 面试回答

Complete knapsack 允许每个 item 被多次使用。

这会改变 iteration order。

在 1D DP 中， capacity 要正序遍历， 这样当前 item 可以在同一轮中继续贡献给后面的 states。

🔟 Complete Knapsack Code

Maximum Value Version

def complete_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(weight, capacity + 1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Key Rule

complete knapsack → capacity forward

为什么正序？

正序允许：

dp[c - weight]

已经包含当前 item。

这就实现了 repeated use。

👉 面试回答

在 complete knapsack 中， 正序遍历 capacity 可以允许同一个 item 被重复使用。

当计算 dp[c] 时， dp[c - weight] 可能已经在当前 item 这一轮使用过当前 item。

这正是 unlimited usage 所需要的。

1️⃣1️⃣ 0/1 vs Complete Knapsack

Main Difference

Pattern Item Usage Capacity Iteration
0/1 Knapsack Use each item once Backward
Complete Knapsack Use each item unlimited times Forward

Why This Matters

同样的 recurrence shape：

dp[c] = best(dp[c], dp[c - weight] + value)

但不同 iteration order 决定了：

current item 是否能被重复使用

👉 面试回答

0/1 和 complete knapsack 的核心区别是 item 是否能重复使用。

0/1 knapsack 中， 我倒序遍历 capacity， 防止当前 item 被重复使用。

Complete knapsack 中， 我正序遍历 capacity， 允许当前 item 被重复使用。

1️⃣2️⃣ Subset Sum

Problem

给定 nums 和 target， 判断是否有 subset 可以 sum to target。

每个 number 只能使用一次。

State Definition

dp[s] = 是否可以形成 sum s

Code

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

为什么是 0/1 Knapsack？

每个 number 只能使用一次。

所以 sum 要倒序遍历。

👉 面试回答

Subset Sum 是 0/1 knapsack。

每个 number 可以选择或不选择。

我定义 dp[s] 为 sum s 是否可以形成。

因为每个 number 只能使用一次， 所以我倒序遍历 sum。

1️⃣3️⃣ Partition Equal Subset Sum

Problem

给定 nums， 判断是否可以把 nums 分成两个 sum 相等的 subsets。

Key Insight

如果 total sum 是 odd：

impossible

如果 total sum 是 even， 我们需要找一个 subset sum 等于：

total // 2

Code

def can_partition(nums):
    total = sum(nums)

    if total % 2 == 1:
        return False

    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

👉 面试回答

Partition Equal Subset Sum 可以转化成 subset sum。

如果 total sum 是 odd， 不可能分成两个相等 subsets。

否则只需要判断是否存在 subset sum 等于 total / 2。

因为每个 number 只能使用一次， 所以这是 0/1 knapsack。

1️⃣4️⃣ Last Stone Weight II

Problem

给定 stones， 每次 smash stones， 要求最后剩下的 weight 最小。

Key Insight

这等价于把 stones 分成两个 groups， 让两个 groups 的 sum difference 最小。

设 total sum 为：

total

如果一组 sum 是：

s

另一组是：

total - s

差值是：

total - 2s

我们希望 s 尽可能大， 但不能超过：

total // 2

Code

def last_stone_weight_ii(stones):
    total = sum(stones)
    target = total // 2

    dp = [False] * (target + 1)
    dp[0] = True

    for stone in stones:
        for s in range(target, stone - 1, -1):
            dp[s] = dp[s] or dp[s - stone]

    for s in range(target, -1, -1):
        if dp[s]:
            return total - 2 * s

    return 0

👉 面试回答

Last Stone Weight II 可以转化成 partition problem。

我们希望把 stones 分成两组， 让两组 sum difference 最小。

所以要找不超过 total / 2 的最大 subset sum。

这是一个 0/1 knapsack subset-sum 问题。

1️⃣5️⃣ Target Sum

Problem

给 nums 中每个 number 添加 + 或 -， 让表达式结果等于 target。

Transformation

设：

P = 加正号的 numbers sum
N = 加负号的 numbers sum

我们需要：

P - N = target
P + N = total

两式相加：

2P = target + total
P = (target + total) / 2

所以问题变成：

count subsets with sum P

Code

def find_target_sum_ways(nums, target):
    total = sum(nums)

    if abs(target) > total:
        return 0

    if (target + total) % 2 == 1:
        return 0

    subset_sum = (target + total) // 2

    dp = [0] * (subset_sum + 1)
    dp[0] = 1

    for num in nums:
        for s in range(subset_sum, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[subset_sum]

为什么倒序？

每个 number 只能被分配一次。

所以这是 0/1 counting knapsack。

👉 面试回答

Target Sum 可以转化为 subset-sum counting。

设正数部分和为 P，负数部分和为 N。

我们有 P - N = target， 且 P + N = total。

推出 P = (target + total) / 2。

所以问题变成： 有多少 subsets 的 sum 等于 P。

1️⃣6️⃣ Coin Change

Problem

给定 coins 和 amount， 返回组成 amount 所需的最少 coins 数。

Coins 可以重复使用。

State Definition

dp[x] = 组成 amount x 所需的最少 coins 数

Code

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

为什么是 Complete Knapsack？

每个 coin 可以无限次使用。

所以 amount 正序遍历。

👉 面试回答

Coin Change 是 complete knapsack。

每个 coin 可以被使用多次。

我定义 dp[x] 为组成 amount x 所需的最少 coins 数。

因为 coin 可以重复使用， 所以对每个 coin，amount 正序遍历。

1️⃣7️⃣ Coin Change II

Problem

给定 coins 和 amount， 返回组成 amount 的 combinations 数量。

Order 不重要。

Example:

amount = 5
coins = [1, 2, 5]

combinations:
5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

answer = 4

Code

def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]

    return dp[amount]

Important Loop Order

对于 order 不重要的 combinations：

coins outer loop
amount inner loop

👉 面试回答

Coin Change II 统计 combinations，不是 permutations。

我把 coins 放在 outer loop， amount 放在 inner loop。

这样每种 combination 只会按 coin 顺序被统计一次。

因为 coins 可以重复使用， 所以 amount 正序遍历。

1️⃣8️⃣ Combination Sum IV

Problem

给定 nums 和 target， 返回 sum to target 的 ordered combinations 数量。

Order matters。

Example:

nums = [1, 2, 3]
target = 4

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1

answer = 7

Code

def combination_sum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for total in range(1, target + 1):
        for num in nums:
            if total >= num:
                dp[total] += dp[total - num]

    return dp[target]

Important Loop Order

对于 order matters 的 permutations：

amount outer loop
nums inner loop

👉 面试回答

Combination Sum IV 统计 ordered combinations。

因为顺序不同也算不同答案， 所以我先遍历 total， 再尝试每个 num 作为最后一个元素。

这样不同顺序会被分别统计。

1️⃣9️⃣ Ones and Zeroes

Problem

给定 binary strings 和两个限制：

m = zeros allowed
n = ones allowed

求最多可以选择多少个 strings。

每个 string 只能使用一次。

State Definition

dp[z][o] = 使用最多 z 个 zeros 和 o 个 ones 时，可以选择的最大 string 数量

Code

def find_max_form(strs, m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count("0")
        ones = s.count("1")

        for z in range(m, zeros - 1, -1):
            for o in range(n, ones - 1, -1):
                dp[z][o] = max(
                    dp[z][o],
                    dp[z - zeros][o - ones] + 1
                )

    return dp[m][n]

为什么倒序？

每个 string 只能使用一次。

这是 two-capacity 0/1 knapsack。

👉 面试回答

Ones and Zeroes 是有两个 capacity dimensions 的 0/1 knapsack。

两个 capacity 分别是 zeros 和 ones。

每个 string 只能选择一次， 所以两个维度都要倒序遍历。

DP value 是最多能选择的 strings 数量。

2️⃣0️⃣ 0/1 Knapsack Counting Variation

Pattern

有时候目标不是 maximize value。

而是 count ways to reach a target。

State:

dp[s] = 形成 sum s 的 ways 数量

Transition:

dp[s] += dp[s - num]

0/1 counting:

iterate s backward

Example

Target Sum 使用这个 pattern。

for num in nums:
    for s in range(target, num - 1, -1):
        dp[s] += dp[s - num]

👉 面试回答

Knapsack 不只是 maximize value。

它也可以用来 count ways to form a target。

如果每个 item 只能用一次， capacity 要倒序遍历。

Transition 是把 previous capacity 的 ways 加到 current capacity。

2️⃣1️⃣ Max Value vs Count Ways vs Feasibility

Three Common DP Meanings

1. Feasibility

dp[s] = 是否可以形成 sum s

Transition:

dp[s] = dp[s] or dp[s - num]

2. Count Ways

dp[s] = 形成 sum s 的 ways 数量

Transition:

dp[s] += dp[s - num]

3. Max / Min Value

dp[c] = capacity c 下的 best value

Transition:

dp[c] = max(dp[c], dp[c - weight] + value)

or:

dp[c] = min(dp[c], dp[c - coin] + 1)

👉 面试回答

Knapsack DP 的 dp 可以有不同含义。

有时 dp 表示某个 sum 是否 possible。

有时 dp 表示 ways 数量。

有时 dp 表示 best value 或 minimum cost。

Recurrence 必须根据 state meaning 来设计。

2️⃣2️⃣ Loop Order Summary

0/1 Knapsack

每个 item 使用一次：

for item in items:
    for capacity in range(C, weight - 1, -1):
        update

Complete Knapsack

每个 item 可以无限使用：

for item in items:
    for capacity in range(weight, C + 1):
        update

Combination Counting

Order 不重要：

for coin in coins:
    for amount in range(coin, target + 1):
        update

Permutation Counting

Order matters：

for amount in range(1, target + 1):
    for num in nums:
        update

👉 面试回答

Loop order 是 knapsack DP 中最重要的细节之一。

0/1 knapsack 中，capacity 倒序。

Complete knapsack 中，capacity 正序。

统计 combinations 时，items 在外层。

统计 ordered permutations 时，target amount 在外层。

2️⃣3️⃣ 常见 Edge Cases

Capacity Is Zero

capacity = 0

通常：

dp[0] = 0

对于 min 或 max value，

或者：

dp[0] = True

对于 feasibility，

或者：

dp[0] = 1

对于 counting ways。

Empty Items

weights = []
nums = []
coins = []

需要根据 target 判断返回值。

Target Impossible

根据问题返回：

False
-1
0

Odd Total Sum

Partition problems 中：

if total is odd, return False

Zero Values

Zeros 会影响 counting problems。

例如 Target Sum 中的 0 会让 ways 翻倍。

👉 面试回答

Knapsack 常见 edge cases 包括 zero capacity、 empty items、 impossible target、 partition problem 中的 odd total sum， 以及 counting problem 中的 zero values。

我会特别注意 dp[0]， 因为它定义了整个 DP 的 base meaning。

2️⃣4️⃣ 常见错误

Mistake 1: Iteration Direction 错误

0/1 knapsack 中使用正序， 会意外重复使用 item。

Mistake 2: Counting Problem Loop Order 错误

Coin Change II 和 Combination Sum IV 的 loop order 不一样。

Mistake 3: Base Case 错误

Counting ways:

dp[0] = 1

Feasibility:

dp[0] = True

Min coins:

dp[0] = 0

Mistake 4: 混淆 Capacity 和 Index

Capacity 是 resource limit。

Index 是 item position。

它们是不同维度。

Mistake 5: 太早做 Space Optimization

先理解 2D recurrence， 再优化成 1D。

👉 面试回答

Knapsack 常见错误包括： capacity iteration direction 错误、 counting problem loop order 错误、 dp[0] base case 错误、 混淆 item index 和 capacity、 以及没有理解 recurrence 就过早优化 space。

我会先判断问题属于： 0/1、complete、feasibility、counting，还是 optimization。

2️⃣5️⃣ 什么时候 Knapsack DP 适用？

Good Fit

当问题涉及：

choose or skip items
capacity constraint
target sum
subset sum
count ways to form target
maximize value under limit
minimize cost under limit
each item used once or unlimited times

Problem Signals

看到这些关键词想到 knapsack：

subset
partition
target sum
capacity
coins
ways to make amount
use each item once
unlimited use
maximum value
minimum number

👉 面试回答

当问题涉及在 capacity 或 target constraint 下选择 items 时， 我会考虑 knapsack DP。

我首先问： 每个 item 能用一次，还是能重复使用？

然后再问： 目标是 feasibility、counting、maximize，还是 minimize？

2️⃣6️⃣ 什么时候 Knapsack DP 不适用？

Not Good Fit

Knapsack DP 不适合：

没有 capacity 或 target dimension
choices 不能形成 reusable subproblems
capacity 太大导致 DP 不现实
问题本质是 shortest path
题目要求列出所有 actual solutions

Better Alternatives

Problem Type Better Pattern
Generate all subsets Backtracking
Shortest path BFS / Dijkstra
Large numeric capacity Greedy / Math / Approximation
Connectivity DFS / Union Find
Range queries Prefix Sum / Segment Tree

👉 面试回答

Knapsack DP 不是所有选择问题都适合。

如果没有 capacity 或 target dimension， 那可能不是 knapsack。

如果 capacity 数值极大， pseudo-polynomial DP 可能太贵。

如果题目要求列出所有 solutions， backtracking 可能更合适。

2️⃣7️⃣ 标准模板

0/1 Knapsack Max Value Template

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(capacity, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

Complete Knapsack Max Value Template

def complete_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for i in range(len(weights)):
        weight = weights[i]
        value = values[i]

        for c in range(weight, capacity + 1):
            dp[c] = max(dp[c], dp[c - weight] + value)

    return dp[capacity]

0/1 Feasibility Template

def can_form_target(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

0/1 Counting Template

def count_subsets(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[target]

Complete Knapsack Min Coins Template

def min_coins(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

Complete Knapsack Count Combinations Template

def count_combinations(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]

    return dp[amount]

Ordered Permutation Count Template

def count_ordered(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for total in range(1, target + 1):
        for num in nums:
            if total >= num:
                dp[total] += dp[total - num]

    return dp[target]

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Knapsack DP 是一类在 capacity 或 target constraint 下选择 items 的 dynamic programming 问题。

最重要的问题是： capacity 是什么， item 是什么， 每个 item 能用一次还是能用多次， 以及目标是 feasibility、counting、maximize，还是 minimize。

在 0/1 knapsack 中， 每个 item 最多使用一次。 经典 state 是 dp[i][c]， 表示使用前 i 个 items， capacity 为 c 时的 best value。

对每个 item， 我们可以 skip 或 take。 如果 skip，答案来自 dp[i - 1][c]。 如果 take，答案来自 dp[i - 1][c - weight] + value。

2D 版本最容易理解。 然后可以优化成 1D， 因为每一行只依赖上一行。

在 1D 0/1 knapsack 中， capacity 必须倒序遍历。 这样可以防止当前 item 在同一轮中被重复使用。

在 complete knapsack 中， 每个 item 可以无限次使用。 因此 capacity 要正序遍历。 这样 dp[c - weight] 可以已经包含当前 item， 从而允许重复使用。

很多 LeetCode 问题都是 knapsack 变体。 Partition Equal Subset Sum 是 subset-sum feasibility。 Target Sum 是通过数学转换后的 subset-sum counting。 Coin Change 是 complete knapsack 的 min coins。 Coin Change II 统计 combinations。 Combination Sum IV 统计 ordered combinations， 所以 loop order 不一样。

一个高级工程师层面的重点是： dp 的含义决定 transition。 如果 dp 表示 feasibility，就用 boolean OR。 如果 dp 表示 count，就累加 ways。 如果 dp 表示 max value，就取 max。 如果 dp 表示 min cost，就取 min。

Loop order 也非常关键。 0/1 usage 要倒序 capacity。 Unlimited usage 要正序 capacity。 Counting combinations 时 item 在外层。 Counting ordered permutations 时 target amount 在外层。

复杂度通常是 O(number of items × capacity)。 这是 pseudo-polynomial complexity， 因为它依赖 capacity 的数值大小， 而不仅仅是 input length。

高级工程师解释 knapsack 时， 我会讲清楚： item 是什么， capacity 是什么， item 使用次数限制是什么， dp[c] 表示什么， 为什么 iteration direction 正确， 以及这个问题是 feasibility、counting、max value 还是 min cost。

⭐ Final Insight

Knapsack DP 的核心不是“背模板”。

它的核心是在 constraint 下选择 items。

Senior-level 的重点是：

item 是什么， capacity 是什么， 每个 item 能不能重复使用， dp 表示 feasibility、count、max value 还是 min cost， loop direction 为什么是 backward 或 forward， 以及 loop order 是否会影响 combination 和 permutation 的计数。

能讲清楚这些， Knapsack 就是一整类 target、capacity、subset、coin change 问题的 DP 建模方法。

Implement