LeetCode - 0/1 Knapsack Problems

LeetCode - 0/1 Knapsack Problems

LAVI
  2026-05-03 2026-05-03 Created   2026-05-04 2026-05-04 Updated      

Medium Hard

416. Partition Equal Subset Sum 494. Target Sum 474. Ones and Zeroes 1049. Last Stone Weight II 2915. Length of the Longest Subsequence That Sums to Target 2787. Ways to Express an Integer as Sum of Powers 879. Profitable Schemes

0/1 背包基本概念

0/1 背包的核心是：每個物品只能選一次

  • 每個 num、每個 stone、每個字串、每個 crime 都只能使用一次
  • 所以更新 dp 時，容量通常要從大到小更新
  • 這樣可以避免同一個物品在同一輪被重複使用

常見寫法：

1
2
3
4
5
for(auto item: items){
    for(int j = target; j >= item; --j){
        dp[j] = ...
    }
}

我的另一篇文章有解說各種背包問題的思路，底家 XD：

Algorithm - DP Knapsack

416. Partition Equal Subset Sum

題目

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解題思路

這題是 0/1 背包
每個數字只能被選一次

  • 先計算總和 total

    • 如果 total 是奇數，不可能分成兩個相等 subset
    • 直接回傳 false

  • 目標變成：

    • 能不能從 nums 裡選一些數字，使總和剛好是 total / 2

  • DP 定義：

    • dp[currSum]：是否可以湊出 currSum

  • 初始化：

    • dp[0] = true
    • 因為什麼都不選，sum 一定為 0

  • 狀態轉移：

    • 每個 num 只能用一次
    • 所以 currSum 要從大到小更新
    • dp[currSum] = dp[currSum] || dp[currSum - num]

  • 最後答案為：
    dp[total]

Solution Code

Time Complexity
O(n × target)

Space Complexity
O(target)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for(auto num: nums) total += num;

        if(total % 2 != 0) return false;
        total /= 2;

        vector<bool> dp(total + 1, false);
        dp[0] = true; // 因為甚麼都不加 sum 一定為 0
        for(auto num: nums){
            for(int currSum = total; currSum >= num; --currSum){
                dp[currSum] = dp[currSum] || dp[currSum - num]; // 去試有沒有可能達到 total 
            }
        }
        return dp[total];
    }
};

494. Target Sum

題目

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

Return the number of different expressions that you can build, which evaluates to target.

Example 1

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.

Example 2

Input: nums = [1], target = 1
Output: 1

Constraints

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

解題思路

這題每個數字都只能用一次
每個數字有兩種選擇：加上去或減掉

  • 先計算 totalSum

    • 如果 abs(target) > totalSum
    • 代表不可能湊出 target，直接回傳 0

  • 因為 sum 可能是負數

    • 所以用 offset 的方式
    • 實際存取時用 sum + totalSum

  • DP 定義：

    • dp[i][sum + totalSum]
    • 代表使用到第 i 個數字時，得到 sum 的方法數

  • 初始化：

    • 第一個數字可以加，也可以減
    • dp[0][totalSum + nums[0]] += 1
    • dp[0][totalSum - nums[0]] += 1

  • 狀態轉移：

    • 枚舉前一層所有可能的 sum
    • 如果以前有更新過
      • 可以選擇加上 nums[i]
      • 也可以選擇減掉 nums[i]

  • 最後答案為：
    dp[nums.size()-1][target + totalSum]

Solution Code

Time Complexity
O(n × totalSum)

Space Complexity
O(n × totalSum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        if(abs(target) > totalSum) return 0;

        vector<vector<int>> dp(nums.size(), vector<int>(2 * totalSum + 1, 0));

        dp[0][totalSum + nums[0]] += 1;
        dp[0][totalSum - nums[0]] += 1;

        for(int i = 1; i < nums.size(); ++i){
            for(int j = -totalSum; j <= totalSum; ++j){ // 就是把 -totalSum ~ totalSum 全跑一遍
                if(dp[i-1][j + totalSum] > 0){ // 代表以前有更新過
                    dp[i][j + totalSum + nums[i]] += dp[i-1][j + totalSum]; // 更新加上 nums[i] 的 dp 那格的值
                    dp[i][j + totalSum - nums[i]] += dp[i-1][j + totalSum]; // 同理，只是是更新減掉 nums[i] 的 dp 那格的值
                }
            }
        }
        
        return dp[nums.size()-1][target + totalSum];
    }
};

474. Ones and Zeroes

題目

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Example 1

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0‘s and 3 1‘s is {"10", "0001", "1", "0"}, so the answer is 4.

Example 2

Input: strs = ["10","0","1"], m = 1, n = 1
Output: 2
Explanation: The largest subset is {"0", "1"}, so the answer is 2.

Constraints

  • 1 <= strs.length <= 600
  • 1 <= strs[i].length <= 100
  • strs[i] consists only of digits '0' and '1'.
  • 1 <= m, n <= 100

解題思路

這題是二維 0/1 背包
每個字串只能選一次

  • 背包容量有兩個維度：

    • 最多可以使用 m 個 0
    • 最多可以使用 n 個 1

  • DP 定義：

    • dp[i][j]：最多使用 i 個 0 和 j 個 1，可以選到的最大 subset size

  • 對每個字串：

    • 先計算這個字串裡有幾個 0
    • 再計算這個字串裡有幾個 1

  • 因為每個字串只能選一次

    • 所以 i 和 j 都要從大到小更新

  • 狀態轉移：

    • 不選目前字串：維持 dp[i][j]
    • 選目前字串：dp[i-zeronum][j-onenum] + 1
    • 因此：
      dp[i][j] = max(dp[i][j], dp[i-zeronum][j-onenum] + 1)

  • 最後答案為：
    dp[m][n]

Solution Code

Time Complexity
O(strs.length × m × n)

Space Complexity
O(m × n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));

        for(auto str: strs){
            int zeronum = 0, onenum = 0;
            for(auto s: str){
                if(s == '0') zeronum++;
                else onenum++;
            }

            for(int i = m; i >= zeronum; --i){
                for(int j = n; j >= onenum; --j){
                    dp[i][j] = max(dp[i][j], dp[i-zeronum][j-onenum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

1049. Last Stone Weight II

題目

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together.

Suppose the stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1

Input: stones = [2,7,4,1,8,1]
Output: 1

Example 2

Input: stones = [31,26,33,21,40]
Output: 5

Constraints

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100

解題思路

這題可以轉成 0/1 背包
目標是把 stones 分成兩堆，讓兩堆重量差最小

  • 設全部石頭總重量為 total

  • 如果其中一堆重量是 sum

  • 另一堆就是 total - sum

  • 最後剩下的重量就是：
    abs(total - sum - sum)

  • 所以問題變成：

    • 找一堆石頭
    • 重量盡量接近 total / 2

  • DP 定義：

    • dp[j]：容量為 j 時，可以裝到的最大石頭重量

  • 每顆石頭只能用一次

    • 所以是 0/1 背包
    • j 要從大到小更新

  • 狀態轉移：

    • dp[j] = max(dp[j], dp[j - stone] + stone)

  • 最後答案為：
    total - 2 * dp[target]

Solution Code

Time Complexity
O(n × total)

Space Complexity
O(total)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int total = accumulate(stones.begin(), stones.end(), 0);
        int target = total / 2;

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

        for(auto stone: stones){
            for(int j = target; j >= stone; --j){
                dp[j] = max(dp[j], dp[j - stone] + stone);
            }
        }

        return total - 2 * dp[target];
    }
};

2915. Length of the Longest Subsequence That Sums to Target

題目

You are given a 0-indexed array of integers nums, and an integer target.

Return the length of the longest subsequence of nums that sums up to target. If no such subsequence exists, return -1.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1

Input: nums = [1,2,3,4,5], target = 9
Output: 3

Example 2

Input: nums = [4,1,3,2,1,5], target = 7
Output: 4

Example 3

Input: nums = [1,1,5,4,5], target = 3
Output: -1

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= target <= 1000

解題思路

這題是 0/1 背包
每個數字只能選一次，目標是湊出 target

  • DP 定義：

    • dp[j]：總和為 j 時，最長 subsequence 長度

  • 初始化：

    • dp[0] = 0
    • 其他設成 INT_MIN
    • 代表目前還湊不出來

  • 對每個 num

    • 因為每個數字只能選一次
    • 所以 j 要從大到小更新

  • 狀態轉移：

    • 選目前的 num
    • dp[j] = max(dp[j], dp[j - num] + 1)

  • 最後：

    • 如果 dp[target] > 0，回傳 dp[target]
    • 否則回傳 -1

Solution Code

Time Complexity
O(n × target)

Space Complexity
O(target)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> dp(target+1, INT_MIN);

        dp[0] = 0;

        for(int num: nums){
            for(int j = target; j >= num; --j){
                dp[j] = max(dp[j], dp[j - num] + 1);
            }
        }
        return (dp[target] > 0) ? dp[target] : -1;
    }
};

2787. Ways to Express an Integer as Sum of Powers

題目

Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1^x + n2^x + ... + nk^x.

Since the result can be very large, return it modulo .

Example 1

Input: n = 10, x = 2
Output: 1
Explanation: We can express n as 3^2 + 1^2 = 10.

Example 2

Input: n = 4, x = 1
Output: 2

Constraints

  • 1 <= n <= 300
  • 1 <= x <= 5

解題思路

這題是 0/1 背包
每個 positive integer 的 x 次方只能使用一次

  • 先枚舉每個數字 i

    • 計算 i^x
    • 如果 i^x 超過 n，後面就不用考慮

  • DP 定義：

    • dp[j]：湊出總和 j 的方法數

  • 初始化：

    • dp[0] = 1
    • 代表湊出 0 有一種方式，就是什麼都不選

  • 因為每個 i^x 只能選一次

    • 所以 j 要從大到小更新

  • 狀態轉移：

    • 這題是求方法數，所以用 +=
    • dp[j] = dp[j] + dp[j - nx]

  • 最後答案為：
    dp[n]

Solution Code

Time Complexity
O(n × n)

Space Complexity
O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numberOfWays(int n, int x) {
        vector<long long int> dp(n+1, 0);
        const int mod = 1e9 + 7;

        dp[0] = 1;

        for(int i = 1; i <= n; ++i){
            long long int nx = pow(i, x);
            for(int j = n; j >= nx; --j){
                dp[j] = (dp[j] + dp[j-nx]) % mod; // 求方法數用 +=
            }
        }
        return dp[n];
    }
};

879. Profitable Schemes

題目

There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can’t participate in another crime.

Let’s call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo .

Example 1

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2

Example 2

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7

Constraints

  • 1 <= n <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

解題思路

這題是二維 0/1 背包
每個 crime 只能選一次

  • 背包容量有兩個維度：

    • 使用的人數 g
    • 達到的 profit p

  • DP 定義：

    • dp[g][p]：用 g 個人，達到 profit 至少 p 的方案數

  • 初始化：

    • dp[0][0] = 1
    • 代表不選任何 crime，也是一種方案

  • 對每個 crime：

    • members = group[i]
    • earn = profit[i]

  • 因為每個 crime 只能選一次

    • 所以 g 要從大到小更新
    • p 也從大到小更新

  • profit 最多只需要記到 minProfit

    • 超過 minProfit 的都壓成 minProfit
    • newProfit = min(minProfit, p + earn)

  • 狀態轉移：

    • 這題是找方法數，所以用 +=
    • dp[g][newProfit] += dp[g - members][p]

  • 最後把所有 dp[g][minProfit] 加起來

    • 因為人數只要不超過 n 都可以

Solution Code

Time Complexity
O(crimes × n × minProfit)

Space Complexity
O(n × minProfit)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        vector<vector<long long int>> dp(n+1 , vector<long long int>(minProfit+1, 0)); // dp[g][p] = 用 g 個人，達到 profit 至少 p 的方案數
        const int mod = 1e9 + 7;

        dp[0][0] = 1;

        for(int i = 0; i < group.size(); ++i){  // group.size() == profit.size() 一樣的
            int members = group[i];
            int earn = profit[i];

            for(int g = n; g >= members; --g){ // dp 第一維是 group，第二維是 profit，所以 for 第二圈從 group 開始更新
                for(int p = minProfit; p >= 0; --p){
                    long long int newProfit = min(minProfit, p + earn);
                    dp[g][newProfit] = (dp[g][newProfit] + dp[g - members][p]) % mod; // 這題是找方法數問題，用 +=
                }
            }
        }

        long long int ans = 0;
        for(int g = 0; g <= n; ++g){
            ans = (ans + dp[g][minProfit]) % mod;
        }
        return ans;
    }
};

Conclusion

0/1 背包的重點是每個物品只能使用一次

  • 如果是一般一維容量

    • 通常用一維 dp
    • 容量從大到小更新

  • 如果有兩種容量限制

    • 例如 0 的數量和 1 的數量
    • 或是人數和 profit
    • 就會變成二維背包

  • 如果是求可不可行

    • 常用 bool dp

  • 如果是求最大值

    • 常用 max

  • 如果是求方法數

    • 常用 +=

最重要的是更新方向：
0/1 背包為了避免同一個物品被重複使用，容量要從大到小更新

On this page
LeetCode - 0/1 Knapsack Problems
  1. 0/1 背包基本概念
  2. 416. Partition Equal Subset Sum
  3. 494. Target Sum
  4. 474. Ones and Zeroes
  5. 1049. Last Stone Weight II
  6. 2915. Length of the Longest Subsequence That Sums to Target
  7. 2787. Ways to Express an Integer as Sum of Powers
  8. 879. Profitable Schemes
  9. Conclusion