【动态规划】背包问题

算法动态规划组合排列

Algorithm

发布日期: 2021-07-01

文章字数: 2.2k

阅读时长: 9 分

阅读次数:

背包定义：

基本定义：给定一个背包容量target，再给定一个数组nums(里面为物品)，能否按一定方式选取nums中的元素并得到target
形式：

背包容量target和物品nums的类型可能是数，也可能是字符串
target可能显示给出，也可能需要从信息中挖掘sum/2

基本背包问题的解题模板：

原始背包问题是一种二维动态规划

void bags()
{
    vector<int> weight = {1, 3, 4};   //各个物品的重量
    vector<int> value = {15, 20, 30}; //对应的价值
    int bagWeight = 4;                //背包最大能放下多少重的物品

    // 二维数组：状态定义:dp[i][j]表示从0-i个物品中选择不超过j重量的物品的最大价值
    vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));

    // 初始化:第一列都是0，第一行表示只选取0号物品最大价值
    for (int j = bagWeight; j >= weight[0]; j--)
        dp[0][j] = dp[0][j - weight[0]] + value[0];

    // weight数组的大小 就是物品个数
    for (int i = 1; i < weight.size(); i++) // 遍历物品(第0个物品已经初始化)
    {
        for (int j = 0; j <= bagWeight; j++) // 遍历背包容量
        {
            if (j < weight[i])           //背包容量已经不足以拿第i个物品了
                dp[i][j] = dp[i - 1][j]; //最大价值就是拿第i-1个物品的最大价值
            //背包容量足够拿第i个物品,可拿可不拿：拿了最大价值是前i-1个物品扣除第i个物品的 重量的最大价值加上i个物品的价值
            //不拿就是前i-1个物品的最大价值,两者进行比较取较大的
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }
    cout << dp[weight.size() - 1][bagWeight] << endl;
}

二维代码可以进行优化，去除选取物品的那一层，简化为一维背包
一维状态定义：dp[j]表示容量为j的背包能放下东西的最大价值

void test_1_wei_bag_problem()
{
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;

    // 初始化
    vector<int> dp(bagWeight + 1, 0);
    for (int i = 0; i < weight.size(); i++)// 遍历物品
        for (int j = bagWeight; j >= weight[i]; j--)// 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //不取或者取第i个
    cout << dp[bagWeight] << endl;
}

代码参考作者：eh-xing-qing

背包问题分类：

按背包类型分类：

0/1背包问题： 每个元素最多选取一次
完全背包问题： 每个元素可以重复选择
组合背包问题： 背包中的物体要考虑顺序

按题目要求分类：

组合个数问题：求所有满足条件的排列组合：
377. 组合总和 Ⅳ
494. 目标和
 518. 零钱兑换 II
70.爬楼梯 (此题也可归类为背包，但其实有更简单的动态规划~放进来是为了更好理解)

组合个数问题公式： dp[i] += dp[i - num]

存在问题：是否存在…:
139. 单词拆分
 416. 分割等和子集

存在问题公式： dp[i] || dp[i - num]

最值问题：要求最大值/最小值:
474. 一和零
 322. 零钱兑换

最值问题公式： dp[i] = max/min(dp[i], dp[i - nums] + 1)

解决问题

解题步骤：

分析是否为背包问题
根据题目要求判断是哪一种背包问题(组合个数，存在，最值)
根据题目信息判断是哪一种背包类型(0/1，完全，组合)

解决方法：

0/1 背包问题：数组中的元素不可重复使用，nums放在外循环，target放在内循环，且循环倒序;

for(num : nums):
    for(i = target; i >= num; i--)
        //if(i >= num) //小于目标的不用再遍历，可以放入循环内，循环到num结束

完全背包问题：数组中的元素可以重复使用，nums放在外循环，target放在内循环，且循环正序；

for(num : nums):
    for(i = num; i <= target; i++)
        //if(i >= num) //小于目标的不用再遍历，可以放入循环内，循环直接从num开始

组合背包问题： 需要考虑元素之间的顺序，target放在外循环，nums放在内循环；
```
for(i = 1; i <= target; i++):
    for(num : nums)
        if(i >= num)
```

这样遇到问题将两个模板往上一套大部分问题就可以迎刃而解~

问题举例

0/1 背包问题：

0/1背包的存在问题
416. 分割等和子集
判断能否将一个数组分割为两个子集，其和相等
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]

思路：题目转化为，是否存在一个子集，使得子集的和为nums数组和的一半，即target = sum(nums) / 2

bool canPartition(vector<int> &nums)
{
    int sum = 0
    for(int num : nums)
    {
        sum += num;
    }
    if (sum % 2 == 1)  //判断和是否为基数
        return false;
    int target = sum / 2; 
    vector<int> dp(target + 1, 0); //dp[i]:是否存在子集和为i

    dp[0] = true;                  //初始化：target=0不需要选择任何元素，所以是可以实现的

    for (int num : nums)                        //外层为nums
        for (int i = target; i >= num; i--)     //内层为target，倒序循环
            dp[i] = dp[i] || dp[i - num];

    return dp[target];
}

0/1背包的组合个数问题
494. 目标和
给数组里的每个数字添加正负号，看是否和能得到target，并求出组合数
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
思路： 参考题解，数组的元素和为sum，
目标和为tar，其中正数的和为x，负数的和为y(正的)，则x + y = sum， x - y = tar，那么x = (sum + tar) / 2;此时x就是本题中要求的”target”

bool findTargetSumWays(vector<int> &nums， int target)
{
    int sum = 0
    for(int num : nums)
    {
        sum += num;
    }
    if ((sum + target) % 2 == 1 || sum < target)  //判断和是否为基数
        return 0;
    int x = (sum + target) / 2; 

    vector<int> dp(x + 1, 0);       //dp[i]:满足i的组合个数为dp[i]个

    dp[0] = 1;                      //初始化：x=0不需要选择任何元素，所以是有一种

    for (int num : nums)                        //外层为nums
        for (int i = x; i >= num; i--)          //内层为target，倒序循环
            dp[i] += dp[i - num];

    return dp[target];
}

完全背包问题：

完全背包的最值问题
322. 零钱兑换
给定amount，求用任意数量不同面值的零钱换到的amount所用的最少数量
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

bool coinChange(vector<int> &coins， int amonut)
{
    vector<int> dp(amount + 1, amount + 1);       //dp[i]:换到i数量所用最少为dp[i]

    dp[0] = 0;                                    //初始化：amonut=0不需要选择任何硬币，所以是有一种

    for (int coin : coins)                        //外层为coins
        for (int i = coin; i <= amount; i++)      //内层为amount，正序循环
            dp[i] = min(dp[i - coin]+1, dp[i]);

    return dp[amount] == amount + 1 ? -1 : dp[amount];
}

组合背包问题：

组合背包的组合个数问题
377. 组合总和 Ⅳ
从nums数组中找出总和为target的元素组合，并返回个数
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：(1, 1, 1, 1),(1, 1, 2),(1, 2, 1)
(1, 3),(2, 1, 1),(2, 2),(3, 1)
请注意，顺序不同的序列被视作不同的组合

int combinationSum4(vector<int>& nums, int target) {
        vector<long> dp(target + 1);                //dp[i]:满足和为i的组合的个数为dp[i]个
        dp[0] = 1;                                  //初始化：target=0的时候可以取空，为1个

        for(int i = 1; i <= target; i++)                    //外层为target
        {
            for(int j = 0; j < nums.size(); j++)            //内层为nums
            {
                if(i >= nums[j] &&  dp[i - nums[j]] < INT_MAX - dp[i])  //此处要保证过程中dp[i]不会超出INT范围
                {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }

        return dp[target];
    }

总结

遇到背包问题，先从题目中提取信息，明确target和nums，判断为哪种背包问题以及哪种题目类型。
总体来说：
如果考虑顺序的组合问题(比如[1,1,2]和[1,2,1]是不同的)，那么外循环只能是target, 内循环只能是nums(target放在外面，这个target的值由nums中的某些组成，得到的是所有种组合可能)；而如果不考虑顺序的组合问题(比如比如[1,1,2]和[1,2,1]是相同的)，那么外循环只能是nums，内循环只能是target(target在内层，得到的是去重后的结果)；这也是组合背包问题和完全背包问题的主要区别。
如果是0/1背包，那么需要采用倒序遍历target，放在内外层无所谓。