动态规划之背包问题

动态规划（dynamic programming）是一种高级的算法，其求解过程中的每一个状态一定是由上一个状态推导出来的，这区别于贪心算法，贪心没有状态推导，而是从局部直接选最优的。动态规划求解问题中比较有名的就是背包问题，当然其能够求解的问题有很多，下面就是可以利用动态规划求解的一些问题（题目源自leetcode，题单来自于代码随想录）

1.背包问题概述

背包问题的分类主要是同一物品的数量不同带来的，分类情况如下图所示：这些背包问题还可以组合形成混合背包问题，大家可以去搜索“背包九讲”查看更加详细的背包问题资料

2. 0-1背包问题

2.1 0-1背包问题模板

0-1背包问题有一个很明显的特征就是每件物品只有一件，这也就是说我们如果选择了这个物品，之后这个物品就没有了。我们用一个二维数组dp来存储状态，只有物品0时，背包容积逐渐增大所能够达到的最大值，接着又多了一个物品1时，背包容积逐渐增大所能够达到的最大值，以此类推最终得到n个物品背包最大体积所能够创造的最大值。（以下面的三个物品，背包容量为4的情况为例子）

采用二维数组dp存储时，需要先初始化dp数组，此时先两层for循环实现的先后顺序可以调换（先遍历物品还是先遍历背包空间都可以），不过建议外层遍历物品，内层遍历空间，这样好理解一些。遍历先后顺序的核心代码对比：

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

    }
}
//==================================
// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

0-1背包题解实现：（模板题）

#include <iostream>
#include<vector>
using namespace std;

int main(){
    int n, volumn;//n是物品数量，volume是背包体积
    cin>>n>>volumn;
    vector<vector<int>> item(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        //输入物品的体积和价值[体积，价值]
        cin>>item[i][0]>>item[i][1];
    }
    vector<vector<int>> dp(n, vector<int> (volumn + 1, 0));
    //初始化dp数组，数组第一行（也就是第一个物品），当背包容积能够装下物品的时候，dp[i][j]就要改成物品一的价值
    for(int j = volumn; j >= item[0][0]; j--){
        dp[0][j] = item[0][1];//初始化第一行，能够放下第一个物品时候，dp[0][j]的价值就为物品一的价值
    }
    //开始0-1背包过程:外层i为物品数量，内层j为背包体积
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= volumn; j++){
            if(j < item[i][0]){//背包体积容不下物品i时，就无需考虑价值变化
                dp[i][j] = dp[i - 1][j];//其最大价值还是体积大小为j，上个一物品时的最大价值
            }else{
                //背包能够容下物品i，这个时候就需要考虑将物品i加入背包了（最大价值变大了就加入）
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i][0]] + item[i][1]);
            }
        }
    }
    cout<<dp[n - 1][volumn];
    
    return 0;
}

上面的代码可以进行空间优化，我们发现每一行的所取到的价值只和上一行最大价值有关，所以我们可以将dp[][]优化为一维dp[]（这里我们从尾到头更新最大价值，这样就不影响我们使用上一行的数据）,代码的实现过程如下：

此时一维数组dp的时候，一定是外层遍历物品，内层遍历背包大小的顺序，不能够够调换

#include <iostream>
#include<vector>
using namespace std;

int main(){
    int n, volumn;//n是物品数量，volume是背包体积
    cin>>n>>volumn;
    vector<vector<int>> item(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        //输入物品的体积和价值[体积，价值]
        cin>>item[i][0]>>item[i][1];
    }
    //此时初始化不需要特殊考虑第一个物品了
    vector<int> dp(volumn + 1, 0);
    //开始0-1背包过程:外层i为物品数量，内层j为背包体积
    for(int i = 0; i < n; i++){
        //内层循环是从尾向前移动（一定要注意！）
        for(int j = volumn; j >= item[i][0]; j--){//背包体积能够装下当前物品i才需要考虑最大价值是否变化
            dp[j] = max(dp[j], dp[j - item[i][0]] + item[i][1]);
        }
    }
    cout<<dp[volumn];
    
    return 0;
}

2.2 分割等和数组

这个题目我们定义背包的容积为数组极限最大和的一半，nums数组中的每一个元素nums[i]就是其value也是其weight，所以动态规划的过程就是在背包容积和数组和一半的时候取得的最大价值能否达到数组和的一半，也就是dp[sum/2] == sum/2是否成立，成立的话说明能够分割成两个元素和相等的子集，否则的话不可以

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //dp[i]中的i表示背包内总和
        //由题目的数据范围知nums总和极限为20000，背包最大只需要其中一半，所以10001大小就行
        vector<int> dp(10001, 0);
        int sum = accumulate(nums.begin(), nums.end(), 0);
			 //如果总和都非偶数，那么一定不可以均分
        if(sum % 2 == 1) return false;
        int target = sum / 2;

        //开始01背包过程(dp[i]中的值一定是小于等于i的)
        for(int i = 0; i < nums.size(); i++){
            for(int j = target; j >= nums[i]; j--){//每一个元素一定是不可以重复放入的，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target) return true;
        return false;
    }
};

2.3 最后一块石头重量 II

这个题目和上面一个题目很像，就是需要想办法将数组和均分，所以题解过程也相似

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum / 2 ;
        vector<int> dp(1501, 0);

        //这个背包问题里面，stones[i]既是weight[i]又是value[i]
        for(int i = 0; i < stones.size(); i++){
            for(int j = target; j >= stones[i]; j--){
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

2.4 目标和（*）

这个题目的题解有两种，第一种方法就是回溯，暴力搜索所有可能的情况：数组 nums 的每个元素都可以添加符号 + 或 -，因此每个元素有2 种添加符号的方法，n个数共有2^n
种添加符号的方法，对应 2^n 种不同的表达式。当 n个元素都添加符号之后，即得到一种表达式，如果表达式的结果等于目标数 target，则该表达式即为符合要求的表达式。

可以使用回溯的方法遍历所有的表达式，回溯过程中维护一个计数器 count，当遇到一种表达式的结果等于目标数 target 时，将 count的值加 1。遍历完所有的表达式之后，即可得到结果等于目标数 target 的表达式的数目。

class Solution {
public:
    int count = 0;

    int findTargetSumWays(vector<int>& nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    void backtrack(vector<int>& nums, int target, int index, int sum) {
        if (index == nums.size()) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
};

第二种方法，动态规划：
因为我们求的是方法数量，所以递推公式变成了dp[i][j] += dp[i - 1][j - num];，请看下面的分析过程：
二维数组dp写法：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

优化为一维数组dp的写法（和上面的写法定义有区别哈）：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        //下面两种情况是没有方案的
        if((target + sum) % 2 == 1) return 0;
        if(abs(target) > sum) return 0;

        int bagSize = (target + sum) / 2;
        //dp[j]表示填满容量j的背包共有dp[j]种方法
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
       
        for(int i = 0; i < nums.size(); i++){
            for(int j = bagSize; j >= nums[i]; j--){
                //01问题涉及到排列组合问题
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

2.5 一和零

这个题目相比前面的题目有又写变化，前面的背包问题只需要考虑物品体积能否装入的背包中就行，而本题中，背包需要考虑两个限制条件：1的数量和0的数量，两个限制条件的0-1背包问题的实现思路还是和之前的是一样的。代码实现如下：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        //dp[i][j]表示最多有i个0和j个1的最大子集大小
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
        //遍历所有物品
        for(string str : strs){
            int oneNum = 0, zeroNum = 0;
            for(char c : str){
                if(c == '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];
    }
};

3.多重背包问题

多重背包问题中，同一个物品的数量是可以无限次选择的。完全背包问题中，无论是一维数组dp还是二维数组dp，其两层循环的先后顺序都可以交换

3.1 多重背包问题模板

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N, volume;
    cin>>N>>volume;
    //用一个vector来存储所有物品[weight, value]
    vector<vector<int>> item (N, vector<int>(2));
    for(int i = 0; i < N; i++){
        cin>>item[i][0]>>item[i][1];
    }
    //完全背包问题在于其同一个物品可以无限次选择
    vector<int> dp(volume + 1, 0);
    //外层遍历物品，内层遍历背包容量
    for(int i = 0; i < N; i++){
        for(int j  = item[i][0]; j <= volume; j++){
            dp[j] = max(dp[j], dp[j - item[i][0]] + item[i][1]);
        }
    }
    cout<<dp[volume];
    return 0;
}

3.2 兑换零钱II(组合问题)

动态规划代码实现：dp[i]表示达到总和i共计有dp[i]种方法

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < coins.size(); i++){
            for(int j = coins[i]; j <= amount; j++){
                //这个题目是一个组合问题
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

3.3 组合总和IV

组合问题：元素顺序不影响结果（外层for循环遍历物品，内层for遍历背包）
排列问题：元素顺序影响结果，不同的顺序算不同的结果（外层for遍历背包，内层for循环遍历物品）

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        //动态规划实现
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        //本题为排列问题
        //如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
        for(int i = 0; i <= target; i++){
            for(int j = 0; j < nums.size(); j++){
                //if(i >= nums[j]) //数据中会有测试导致 dp[i] += dp[i - nums[j]]超过int的最大值
                if(i >= nums[j] && dp[i] < INT_MAX - dp[i - nums[j]]){
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

3.4 零钱兑换

dp[i]:当钱币种类coins[0：i]时，达到amount使用最少的钱币数量

class Solution {
public:
    //这是一个组合问题
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp (amount + 1, INT_MAX);
        dp[0] = 0;//这里就表示空间为零的硬币个数一个也没有，所以最小硬币个数为0
        for(int i = 0; i < coins.size(); i++){
            for(int j = coins[i]; j <= amount; j++){
                if(dp[j - coins[i]] < INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

3.5 完全平方数

像这些求元素最少数量或者元数最大数量的题目，当成组合问题和排列问题都没关系，排列问题和组合问题的差别只在解的数量上会有差异，但是解的最大长度和最小长度是不变的

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        //完全背包：组合问题(这个题目时求个数最小，所以排列解法还是组合解法都没有问题)
        for(int i = 0; i <= n; i++){//遍历背包
            for(int j = 1; j * j <= i; j++){//遍历物品
                dp[i] = min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
};

3.6 单词拆分（*）

这个里dp[i]表示的含义不同于以往：dp[i] == true表示s[0:i]可以拆分成wordDict中的词

class Solution {
public:
    //这个题目可以用回溯优化实现，下面时动态规划实现的
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        //dp[i]:true表示s[0:i]可以拆分成wordDict中的词
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(int i = 1; i <= s.size(); i++){
            for(int j = 0; j < i; j++){
                string word = s.substr(j, i - j);
                if(wordSet.find(word) != wordSet.end() && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

4. 多重背包问题

多重背包问题中，物品的数量既不是唯一的，又不是无限多个的。我们可以通过某些转变一下思维，假设物品item有5个，每一个价值为2，那么是不是可以看成物品集中有5个不同的物品，但是它们的价值都是2，这样的话，**将多重背包问题转化为了0-1背包问题，**每个物品数量都是唯一的。

如何实现多个相同的物品拆解成多个不同单物品？这个过程只需要再添加一个for循环就能够实现啦，见下面的代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    //物品个数，背包容积
    int N, V;
    cin>>N>>V;
    vector<int> volumn(N), value(N), count(N);
    //输入物品信息[体积，价值，数量]
    for(int i = 0; i < N; i++){
        cin>>volumn[i]>>value[i]>>count[i];
    }
    vector<int> dp(V + 1, 0);
    //将多重背包问题拆解成0-1背包问题
    for(int i  = 0; i < N; i++){
        for(int j = V; j >= volumn[i]; j--){
            //如果物品数量不止一个，那么进行拆解单个物品
            for(int k = 1; k <= count[i] && (j - k * volumn[i] >= 0); k++){
                dp[j] = max(dp[j], dp[j - k * volumn[i]] + k * value[i]);
            }
        }
    }
    cout<<dp[V];
    return 0;
}