背包问题详解C++版.md

背包问题原理具体解析：dd大牛的《背包九讲》

1、01背包问题

题目：有$N$件物品和一个容量为$V$的背包，第$i$件物品的容量是$cost[i]$，价值是$w[i]$，求解将哪些物品放入背包，可以在背包容量允许的情况下，物品价值和最大。

特点：只有一个背包，每个物品只有一个。

函数：$f[i][j] $表示将前$i$件物品放入容量为$j$的背包中时，物品的最大价值。

状态转移方程：

$$
f[i][j] = max(f[i-1][j],f[i-1][j-cost[i]]+w[i])
$$

在空间上将二维转化为一维：

$$
f[j] = max(f[j],f[j-cost[i]]+w[i])
$$

代码：

1
2
3
4
5
6
7
8
vector<int>dp(V+1,0);
for(int i = 0;i<N;i++){
    //循环是从后往前的
    for(int j = V;j>=cost[i];j--){
        dp[j] = max(dp[j],dp[j-cost[i]]+w[i]);
    }
}

分割等和子集

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

特点：只有一个背包，每个物品只有一个。

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

转化为01背包问题：

背包容积为数组nums元素和的一半（假设为target），从数组中提取数字，使总容量恰好为target。

函数：$f[i][j]$表示数组的前$i$个元素中是否有和为$j$的组合，布尔类型。

状态转移方程：

$$
f[i][j] = f[i-1][j]||f[i-1][j-nums[i]]
$$

在空间上将二维转化为一维：

$$
f[j] = f[j]||f[j-nums[i]]
$$

代码：

1
2
3
4
5
6
7
8
9
vector<bool>dp(target+1,false);
//注意初始化
dp[0] = true;
for(int i = 0;i < n;i++){
    //注意j的临界条件
    for(int j = target;j>=nums[i];j--){
        dp[j] = dp[j]||dp[j-nums[i]];
    }
}

目标和

题目：

给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

转化为01背包问题：

这是一个比较隐晦的背包问题，需要我们进行进一步的转换才能看出来。

假设前面所有加了-号的整数，其和为neg，前面所有加了+号的整数，其和为pos，nums数组的总和为sum，于是就有:

$neg+pos = sum$

$−neg+pos=target$

所以有：$neg=(sum-target)/2$

即，从数组nums中选取若干个数字，使其和等于neg即可。

特点：只有一个背包，每个物品只有一个。

函数：$f[i][j]$表示数组的前$i$个元素中和为$j$的组合数量。

状态转移方程：

$$
f[i][j] = sum(f[i-1][j],f[i-1][j-nums[i]]+1)
$$

在空间上将二维转化为一维：

$$
f[j] = sum(f[j],f[j-nums[i]]+1)
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto num:nums){
            sum+=num;
        }
        if(sum<target) return 0;
        if((sum-target)%2==1) return 0;
        int neg = (sum-target)/2;
        vector<int>dp(neg+1,0);
        dp[0]=1;
        int n = nums.size();
        for(int i=0;i<n;i++){
            for(int j=neg;j>=nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[neg];
    }

最后一块石头的重量（二）

题目：

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

转化为01背包问题：

这依旧是一个比较隐晦的背包问题，与上题相似，需要我们进行进一步的转换才能看出来。

用归纳法可以证明，无论按照何种顺序粉碎石头，最后一块石头的重量总是可以表示成

$$
\sum_{i=0}^{n-1} k_i \times stones_i, k_i \in{-1,1}
$$

上述和式得到的最小非负和即为本题的答案。

记石头的总重量$sum$，标记为-1的石头的重量之和为$ neg$，则其余的石头的重量之和为$sum-neg$。则有

$$
\sum_{i=0}^{n-1} k_i \times stones_i=(sum-neg)-neg=sum-2\times neg
$$

要使最后一块石头的重量尽可能地小，$neg $需要在不超过 $⌊sum/2⌋ $的前提下尽可能地大。因此本问题可以看作是背包容量为 $⌊sum/2⌋$，物品重量和价值均为$stones[i]$的 0-1 背包问题。

特点：只有一个背包，每个物品只有一个。

函数：$f[i][j]$表示数组的前$i$个石头放入容积为$j$的背包的最大重量。

状态转移方程：

$$
f[i][j] = max(f[i-1][j],f[i-1][j-stones[i]]+stones[i])
$$

在空间上将二维转化为一维：

$$
f[j] = max(f[j],f[j-stones[i]]+stones[i])
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        if(n == 1)return stones[0];
        if(n == 2)return abs(stones[0]-stones[1]);
        int sum = 0;
        for(auto num:stones){
            sum+=num;
        }
        int target = sum/2;
        vector<int>dp(target+1,0);
        for(int i = 0;i<n;i++){
            for(int j = target;j>=stones[i];j--){
                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }

2、完全背包问题

题目：有$N$种物品和一个容量为$V$的背包，每个物品有无限个，第$i$件物品的容量是$cost[i]$，价值是$w[i]$，求解将哪些物品放入背包，可以在背包容量允许的情况下，物品价值和最大。

特点：只有一个背包，每个物品有无数个。

函数：$f[i][j] $表示将前$i$件物品放入容量为$j$的背包中时，物品的最大价值。

状态转移方程：

$$
f[i][j] = max(f[i-1][j],f[i-1][j-cost[i]]+w[i])
$$

在空间上将二维转化为一维：

$$
f[j] = max(f[j],f[j-cost[i]]+w[i])
$$

代码：

1
2
3
4
5
6
7
vector<int>dp(V+1,0);
for(int i = 0;i<N;i++){
    //从前往后
    for(int j = cost[i];j<=target;j++){
        dp[j] = max(dp[j],dp[j-cost[i]]+w[i]);
    }
}

完全平方数

问题：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。（注：所有正整数都可以由完全平方数相加得来，因此此题一定为true，与下题的零钱兑换区分开。）

特点：只有一个背包，但每个数字可以有无数个。

转化为完全背包问题：

背包容积为n，要从小于n的所有完全平方数中抽取最少数量的数字，使得其和为n。其中每个数字可以被抽取的次数不限。

函数：$f[i][j] $表示将前$i$个完全平方数放入容量为$n$的背包中时，需要的最少数量。

状态转移方程：

$$
dp[i][j] = min(dp[i-1][j],dp[i-1][j-package[i]]+1)
$$

在空间上将二维转化为一维：

$$
dp[j] = min(dp[j],dp[j-package[i]]+1)
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int numSquares(int n) {
        vector<int>package;
        for(int i=0;i*i<=n;i++){
            package.push_back(i*i);
        }
        //完全背包问题，找最小值
        vector<int>dp(n+1,10000);
        //初始化
        dp[0] = 0;
        int len = package.size();
        for(int i = 0;i<len;i++){
            //从前往后
            for(int j = package[i];j<=n;j++){
                dp[j] = min(dp[j],dp[j-package[i]]+1);
            }
        }
        return dp[n];
    }

零钱兑换

问题：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

特点：只有一个背包，但每个硬币可以有无数个。

转化为完全背包问题：

背包容积为amount，从硬币中抽取最少数量的硬币，使得其和为amount。其中每个硬币可以被抽取的次数不限。

函数：$f[i][j] $表示将前$i$个硬币凑成金额为$amount$时，需要的最少数量。

状态转移方程：

$$
dp[i][j] = min(dp[i-1][j],dp[i-1][j-coins[i]]+1)
$$

在空间上将二维转化为一维：

$$
dp[j] = min(dp[j],dp[j-coins[i]]+1)
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int coinChange(vector<int>& coins, int amount) {
        //dp[i][j] 前i种硬币凑成j钱所需要的最少的硬币个数
        //状态转移方程 
        if(amount == 0) return 0;
        int n = coins.size();
        vector<int>dp(amount+1,10000);
        dp[0]=0;
        for(int i = 0;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j] = min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount] == 10000? -1:dp[amount];
    }

零钱兑换（二）

问题：

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。

转化为完全背包问题：

背包容积为amount，从硬币中抽取最少数量的硬币，使得其和为amount。其中每个硬币可以被抽取的次数不限。

函数：$f[i][j] $表示将前$i$个硬币凑成金额为$amount$时，可以凑成功的组合数。

状态转移方程：

$$
dp[i][j] = sum(dp[i-1][j],dp[i-1][j-coins[i]])
$$

在空间上将二维转化为一维：

$$
dp[j] = sum(dp[j],dp[j-coins[i]])
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
int change(int amount, vector<int>& coins) {
        vector<int>dp(amount+1,0);
        dp[0] = 1;    //当需要凑的金额为0时，只有一种组合法，即什么都不选。
        int n = coins.size();
        for(int i=0;i<n;i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j] = dp[j]+dp[j-coins[i]];
            }
        }
        return dp[amount];
    }

3、多重背包问题

题目：有$N$种物品和一个容量为$V$的背包，每个物品数量有限，第$i$件物品的容量是$cost[i]$，价值是$w[i]$，数量是$k[i]$，求解将哪些物品放入背包，可以在背包容量允许的情况下，物品价值和最大。

特点：只有一个背包，每个物品数量有限且不一定相等。

函数：$f[i][j] $表示将前$i$件物品放入容量为$j$的背包中时，物品的最大价值。

状态转移方程：（k为当前放入i号物品的数量）

$$
f[i][j] = max(f[i-1][j],f[i-1][j-cost[i]*k]+w[i]*k)
$$

在空间上将二维转化为一维：

$$
f[j] = max(f[j],f[j-cost[i]*k]+w[i]*k)
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int package(int volumn,vector<int>weights, vector<int>values, vector<int>nums){
    //分别表示背包容积，每一个物品的大小，价值和数量
    int len = weights.size();
    vector<int>dp(volumn+1,0);
    //f[i][j]表示将前i件物品放入容量为j的背包中时，物品的最大价值。
    for(int i = 0;i<len;i++){
        for(int j = volumn;j>=weights[i];j--){
            for(int k = 0;k<=nums[i]&&k*weights[i]<=j;k++){
                dp[j] = max(dp[j],dp[j-k*weights[i]]+k*values[i]);
            }
        }
    }
    return dp[volumn];
}

4、多维背包问题

题目：有$N$种物品要放入背包中，每个物品的体积为$v[i]$，价值为$w[i]$，但是限制条件不止一个，例如背包中物品的总重量不能大于$V$且物品的总价值为$W$，求解这种条件下物品放置的策略。（每个物品只能选一次）

特点：不止一个背包，但每个物品只有一个。

函数：当限制的数量增多时，我们也需要增加函数的维度。$f[i][j][k] $表示将前$i$件物品放入容量为$j$的背包中价值为$k$的物品的组合数量。

状态转移方程：

$$
f[i][j][k] = sum(f[i-1][j][k],f[i-1][j-v[i]][k-w[i]])
$$

在空间上将二维转化为一维：

$$
f[j] = max(f[j],f[j-v[i]][k-w[i]])
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
vector<vector<int>>dp(V+1,vector<int>(W+1,0));
        //初始化
        for(int i=0;i<=N;i++){
            dp[i][0]=1;
        }  

        for(int i=0;i<v.size();i++)
            for(int j=V;j>=v[i];j--)
                for(int k=W;k>=w[i];k--){
                    dp[j][k] = dp[j][k]+dp[j-group[i]][k-w[i])];
                }

盈利计划

问题：

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。第 i 种工作会产生$ profit[i] $的利润，它要求 $group[i] $名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。工作的任何至少产生 $minProfit $利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

转化为完全背包问题：

等价于，背包容积为$n$，每个物品的价值为$profit$，每个物品的体积为$group$，求放入背包中价值不小于$minProfit$的组合数量

函数：$f[i][j][k] $表示 前i个物品，在背包容积为j的情况下，价值不小于k的组合数量。

状态转移方程：

$$
dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-group[i]][max(0,k-profit[i])]
$$

为什么是max？因为如果像之前一样的写法不加max，则就变成了利润恰好为minProfit的组合数量。此处希望利润可以大于等于minProfit，当我们选择加入第i个物品时，如果k-profit[i]<0，就意味着你本身加进来的这第i个物品的价值就已经大于你在此处循环里设置的k值了，那么这种情况当然也是要count在内的，所以此处我们就直接将k设置为0，将k=0时的组合数加起来。

在空间上将二维转化为一维：

$$
dp[j][k] = dp[j][k]+dp[j-group[i]][max(0,k-profit[i])]
$$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    vector<vector<int>>dp(n+1,vector<int>(minProfit+1,0));
    int len = group.size(), MOD = (int)1e9 + 7;
    for(int i=0;i<=n;i++){
        dp[i][0]=1;
    }  
    for(int i=0;i<len;i++)
        for(int j=n;j>=group[i];j--)
            for(int k=minProfit;k>=0;k--){
                dp[j][k] = (dp[j][k]+dp[j-group[i]][max(0,k-profit[i])])%MOD;
            }
    return dp[n][minProfit];
}

一和零

题目：

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

转化为完全背包问题：

等价于，从数组strs中取元素放入背包中，限制条件是0的数量不超过m个，1的数量不超过n个，并且每个元素只能取一次。很明显是多维背包问题。

函数：$f[i][j][k] $表示数组的前i个元素，在0的数量不超过j，1的数量不超过k的情况下的组合数量。

状态转移方程：

$$
dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-count0][k-count1]+1)
$$

其中，$count0$是数组第$i$个元素中0的数量，$count1$是数组第$i$个元素中1的数量。

在空间上将二维转化为一维：

$$
dp[j][k] = max(dp[j][k],dp[j-count0][k-count1]+1)
$$

代码：

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
28
29
30
vector<int> count01(string str){
        int n=str.size();
        int countm=0;
        int countn=0;
        for(int i=0;i<n;i++){
            if(str[i] == '0') countm++;
            else countn++;
        }
        vector<int>s;
        s.push_back(countm);
        s.push_back(countn);
        return s;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        int len = strs.size();
        for(int i=0;i<len;i++){
            vector<int>res = count01(strs[i]);
            int count0 = res[0];
            int count1 = res[1];
            for(int j=m;j>=count0;j--){
                for(int k=n;k>=countn1;k--){
                    dp[j][k] = max(dp[j][k],dp[j-count0][k-count1]+1);
                }
            }
        }
        return dp[m][n];

    }

总结

背包种类 背包个数 每个物体数量 限制条件个数 内层循环方向 循环层数 函数维度
01背包 1 1 1 从后往前 2 1
完全背包 1 无数 1 从前往后 2 1
多重背包 1 nums[i] 1 从后往前 3 1
多维背包 n 1 n 从后往前 2 n