在动态规划的世界里，0-1 背包问题绝对是基础且重要的存在。它的核心思想是在给定背包容量和物品价值、重量的情况下，选择物品放入背包，使得总价值最大，且每个物品最多选一次。今天，我们就围绕 0-1 背包，结合几道经典题目来深入剖析。

在算法领域，“背包” 是一类经典的动态规划问题模型，核心是在给定资源限制（类似背包的容量）下，选择物品（有各自的 “重量”“价值” 等属性），以达到某种最优目标（如总价值最大、满足特定和等）。

以 0 - 1 背包为例，“背包” 可以理解为：有一个容量有限的容器（背包），面对若干物品，每个物品有重量和价值，且每个物品最多选一次，要选出物品放入背包，使得在不超过背包容量的前提下，总价值最大。这里的 “背包” 就是那个承载物品、有容量限制的抽象载体，而各类背包问题就是围绕如何在这个载体的限制下做最优选择展开的。像前面提到的分割等和子集问题，就可以把数组元素看作物品，“背包” 容量是数组总和的一半，目标是看能否选出元素 “装满” 这个 “背包”；目标和问题则是通过转化，把找目标和的方案数转化为在特定 “背包” 容量下选元素的组合数等。

一、0-1 背包的基本模型

假设我们有n个物品，每个物品的重量为weight[i]，价值为value[i]，背包的容量为bagSize。我们定义dp[i][j]表示从前i个物品中选，且背包容量为j时能获得的最大价值。

状态转移方程为

• 不选第i个物品：dp[i][j] = dp[i - 1][j]。
• 选第i个物品（前提是背包能装下）：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]。

最终的结果就是dp[n][bagSize]。

为了优化空间复杂度，我们还可以使用一维数组dp[j]，此时状态转移方程为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，但要注意遍历背包容量时要从后往前遍历，防止物品被重复选择。

二、经典题目实战

（一）416. 分割等和子集

题目大意：给定一个只包含正整数的非空数组nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

分析：这是一个典型的 0-1 背包应用。我们需要判断是否存在一个子集，其和为数组总和的一半。数组中的每个元素相当于物品，元素的值相当于重量和价值（这里只关注重量，因为要凑和），背包容量为总和的一半。如果dp[target] == target（target为总和的一半），则说明可以分割。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //计算数组和
        int s = reduce(nums.begin(),nums.end());
        if(s % 2){//如果是和是奇数 返回false
            return false;
        }
        int n = nums.size();
        vector memo(n,vector<int>(s / 2 + 1,-1));//-1表示没有计算过
        auto dfs = [&](this auto&&dfs,int i,int j)->bool{
            if(i < 0){
                return j==0;
            }
            int& res = memo[i][j];
            if(res!=-1){//利用缓存
                return res;
            }
            if(j < nums[i]){
                return res = dfs(i-1,j);//只能不选
            }
            return res = dfs(i-1,j) || dfs(i-1,j - nums[i]);//选或不选
        };
        return dfs(n-1,s/2);

    }
};

（二）494. 目标和

题目大意：给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加'+'或'-'，然后串联起来构成一个表达式，求可以得到target的不同表达式的数目。

分析：设添加'+'的数的和为sum_plus，添加'-'的数的和为sum_minus，则有sum_plus - sum_minus = target，且sum_plus + sum_minus = sum(nums)。联立可得sum_plus = (sum(nums) + target) // 2。问题就转化为在数组中选若干个数，使得它们的和为sum_plus，求这样的组合数，这也是 0-1 背包问题，只不过这里要计算的是方案数，而非最大价值。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = reduce(nums.begin(),nums.end()) - abs(target);
        if(s < 0 || s % 2){//奇数或者负数 无法达到 返回false
            return false;
        }
        int m = s / 2;
        int n = nums.size();
        vector memo(n,vector<int>(m + 1 , -1));//-1表示没有计算过
        auto dfs = [&](this auto&& dfs,int i,int j)->int{
            if(i < 0){
                return j == 0;
            }
            int &res = memo[i][j];
            if(res!=-1){//缓存中有
                return res;
            }
            if(j <nums[i]){
                return res = dfs(i-1,j);//只能不选
            }
            return res = dfs(i-1,j) + dfs(i-1,j-nums[i]);//选或者不选的和 -- 加法原理
        };
        return dfs(n-1,m);
    }
};

（三）474. 一和零（二维背包）

题目大意：给你一个二进制字符串数组strs和两个整数m和n。请你找出并返回strs的最大子集的长度，该子集中最多有m个0和n个1。

分析：这是二维费用的 0-1 背包问题。每个字符串有两个 “重量”，即0的个数和1的个数，“价值” 是字符串的长度。我们需要在0的数量不超过m、1的数量不超过n的情况下，选择字符串，使得总长度最大。定义dp[i][j]表示使用i个0和j个1时能得到的最大字符串长度。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> cnt0(strs.size());
        for (int i = 0; i < strs.size(); i++) {
            cnt0[i] = ranges::count(strs[i], '0');
        }
        vector memo(strs.size(),
                    vector(m + 1, vector<int>(n + 1, -1))); //-1表示没有计算过
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i < 0) {
                return 0;
            }
            int& res = memo[i][j][k]; // 注意这里是引用
            if (res != -1) {
                return res;
            }
            res = dfs(i - 1, j, k); // 不选strs[i]
            int cnt1 = strs[i].size() - cnt0[i];
            if (j >= cnt0[i] && k >= cnt1) {
                res = max(res,
                          dfs(i - 1, j - cnt0[i], k - cnt1) + 1); // 选strs[i];
            }
            return res;
        };
        return dfs(strs.size() - 1, m, n);
    }
};

三、总结

0-1 背包问题是动态规划中的经典模型，很多问题都可以转化为 0-1 背包来解决。关键在于如何将实际问题中的元素与背包问题中的物品、重量、价值等概念对应起来。通过对这几道题目的分析，我们可以看到，无论是分割等和子集、计算目标和的方案数，还是处理二维背包的一和零问题，都离不开 0-1 背包的核心思想。掌握了 0-1 背包，再去解决更复杂的动态规划问题，就会更加得心应手。