Leetcode动态规划—完全背包问题_完全背包问题 leetcode

内容参考

https://blog.csdn.net/yoer77/article/details/70943462

https://labuladong.github.io/ebook/动态规划系列/

https://leetcode-cn.com/problems/coin-change/solution/bei-bao-wen-ti-zhi-01bei-bao-wen-ti-ke-pu-wen-ji-c/

前文：Leetcode动态规划——01背包问题 ： https://blog.csdn.net/qq_41605114/article/details/106059876

 

动态规划一般解决最值问题，题目只要问最值，但是不在乎得到最值的解法，基本可以考虑使用动态规划解决问题。

动态规划的部分问题可以归类为背包问题，下面介绍背包问题中最基础也是理解动态规划和所有背包问题的关键！

目录

完全背包

【状态】

【状态方程】

【初始化（base case）】

【关于空间优化】

总结

322. 零钱兑换

518. 零钱兑换 II

如果考虑到组合的顺序问题：377. 组合总和 Ⅳ

其余完全背包问题

---

完全背包

有N个物品，该物品有两个属性，重量w[i]，价值v[i]。

有背包一个，承重为W。

现在要求从这些物品中挑选出总重量不超过W的物品

求所有挑选方案中价值总和的最大值

每件物品可以挑选多件

在01背包问题中，每件物品只有放入或者不放两种选择，但是完全背包问题中，，第i件物品可以放进背包的个数范围【0，W/w[i]】

 

【状态】

我们定义dp函数如下：

 

 根据是否要求背包满载，分为两种情况，

1. 在背包满载的情况下，所能取得的最大价值是多少
2. 在背包可以不满载的情况下，所能取得的最大价值是多少

动态规划的核心，就是问题的分解，将复杂问题分解为有限个子问题（重叠子问题），求解子问题的最优解（最优子结构），

然后，将子问题和父问题联系起来（状态方程），过程中注意避免重复计算一些子问题（重叠子问题）。

那么我们给出了子问题的结构，也就是dp[i][j]。

如何将这个子问题和父问题联系起来呢？我们来看看dp[i][j]是怎么构成的：

解释：

1. 如果拿了，那么第i-1的最优解加上第i个的价值（此时注意，剩余重量要改变），拿了第j件几个就相应的改变多少，就是拿了第i个的最优解！
2. 如果不拿，那么就是第i-1的最优解。此时的j可能需要根据题意来判断了，有时要求装满有时要求无所谓，但是这都不影响大局，只要不超出负重就行。

那么不可能以上两种情况兼得，取最优即可，取二者中的最值。

【状态方程】

如下： 

 

 目前为止，父问题和子问题都已经联系到一起了，也找到了最优子结构的部分。在代码部分注意重叠子问题，如果计算过的部分大可不必再算。

我们手动推导一下状态方程执行的过程，看看问题所在

        

其实整个动态规划就是在填这个变，i的起点是1，终点是2，j的起点是1，终点是5，i和j均为零的情况没有意义，单纯的在初始化中全部初始化为0即可。

程序也是这么指向的，从上面表格黑色部分的左上角开始，按照行遍历

（但是要注意，题目一旦对达到最优解时背包一定要满载，那么初始化情况会有所变化） 

表中的内容就是在第1~i个物品中挑选，在不超出规定的重量下，计算得出的最大价值。

表中红色内容，都是需要我们初始化（base case）的，而且也都是容量太小，一个物品也放不进去的情况。

从表中也可以看出，我们dp初始化的大小一定要是（n+1）x（w+1）,因为第i个元素，在数组中的下标是i-1。

我们要求dp【n】【w】,大小自然是（n+1）x（w+1）

 

模板（记忆化递归）：

#include <iostream>
#include <cstring>
#define MAXN 1000
using namespace std;
 
int dp[MAXN][MAXN];
int w[MAXN] = {2, 1, 3, 2};
int v[MAXN] = {3, 2, 4, 2};
int W = 7, n = 3;
 
int solve(int n, int W) {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            for (int k = 0; k <= j/w[i]; k++) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*w[i]] + k*v[i]);
            }
        }
    }
    return dp[n][W];
}
 
int main() {
    cout << solve(n, W) << endl; // 10
    return 0;
}

（来源：https://blog.csdn.net/yoer77/article/details/70943462） 

以上内容其实存在较多的冗余，现在将状态方程简化：

 

关于不选择第i个物品，自然是第1到i-1个物品进行j重量的拼凑。

那么选择第i件物品，总的重量减少，这是一定的，但是由于是完全背包问题，不是01背包，完全背包每个物品可以任意挑选，不是01背包只能选一次；

01背包只能选择一次，所以必须是dp[i-1][j-w[i]]+v[i]，因为i-1中的-1，就是保证前全部的内容中不会选择第i个，选择了第i个后，末尾才会加上一个v[i]。

但是完全背包不在乎，任意选择即可。

#include <iostream>
#include <cstring>
#define MAXN 1000
using namespace std;
 
int dp[MAXN][MAXN];
int w[MAXN] = {2, 1, 3, 2};
int v[MAXN] = {3, 2, 4, 2};
int W = 7, n = 3;
 
int solve(int n, int W) {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < w[i]) {// 不能塞的时候也不能硬塞，要注意一下
                dp[i][j] = dp[i-1][j];
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]);
            }
        }
    }
    return dp[n][W];
}
 
int main() {
    cout << solve(n, W) << endl; // 10
    return 0;
}

（来源：https://blog.csdn.net/yoer77/article/details/70943462） 

 

【初始化（base case）】

以上内容是方法论，理解起来可能有些抽象，那么看几道实例，有助于理解

【关于空间优化】

参考：https://www.cnblogs.com/yxym2016/p/12684203.html

 

具体推导过程参考01背包，完全背包也是一样的，可以压缩空间

#include <iostream>
#include <cstring>
#define MAXN 1000
using namespace std;
 
int dp[MAXN];
int w[MAXN] = {2, 1, 3, 2};
int v[MAXN] = {3, 2, 4, 2};
int W = 7, n = 3;
 
int solve(int n, int W) {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < w[i]) {
                dp[j] = dp[j];
            }
            else {
                dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            }
        }
    }
    return dp[W];
}
 
int main() {
    cout << solve(n, W) << endl; // 10
    return 0;
}

和01背包代码的区别，也只剩下内循环的方向不一样了，01背包是逆序，因为必须保证dp[i][j]的状态是由dp[i-1]推导而来的。

也是为了能保证每个物品只选择一次，保证在考虑入选第i件物品时，依据的是绝对没有选入i的dp[i-1]推导而来的。

而现在完全背包，自然是不在乎这种问题，物品可以挑选无数个，只要能得到最优解即可。

除了内循环不一样以外，其他内容全部一样！

总结

不仅仅是背包问题，动态规划的所有问题，都是按照下面的思维模式进行解决的。

题目只要问最值，但是不在乎得到最值的解法，基本可以考虑使用动态规划解决问题

【状态】：问题求什么，要什么，我们dp的因变量就是什么，自变量根据题目要求，为物品和容量

【状态方程】确定好了状态，就要看看这个父问题如何转换为子问题了，这也是状态方程要解决的

【初始化】主要是看有没有要求得到最值的时候，满负载

【考虑压缩空间】自变量如果能从物品和容量单纯的变成容量，那自然是好事

 

以上都是方法论，我们看看Leetcode中典型的完全背包问题，看看如何入手解决：

 

---

322. 零钱兑换

https://leetcode-cn.com/problems/coin-change/

请忘记什么模板，在没有模板的情况下，这道题我们应该如何思考？

直觉告诉我们，dp可以这么设置，dp[i][j] = 从1到i个硬币中进行挑选，组成金额为j的最少硬币个数。 

那么状态方程怎么写呢？还是比较简单的，遇到硬币，就两种选择,拿与不拿，根据拿与不拿进行比较即可

下面我们直接上dp table，一窥如何初始化

关于初值： 

从第一行，i=1看起，dp[1][1] = min（dp[1][0]+1，dp[0][1]），此时dp[0][j]必须全部初始化为正无穷（无效状态）

从逻辑上来看，没有硬币，根本就没有办法凑成任何的金额，从动态规划迭代的思路上来看，整个迭代过程必须是让dp[0][j]全部失效。

不进行优化的程序如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        if(n == 0) return 0;
        vector<vector<int>> dp(n+1,vector<int>(amount+1,amount+1));
        for(int i = 0;i<=n;++i) dp[i][0] = 0;//金额0，使用0个硬币
        for(int i = 1;i<=n;++i)
        {
            for(int j = 1;j<=amount;++j)
            {
                if(j-coins[i-1]>=0)
                dp[i][j] = min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                else
                dp[i][j] = dp[i-1][j];
            }
        }
        return (dp[n][amount] == amount+1)?-1:dp[n][amount];
    }
};

关于优化：

整个迭代是一行一行进行的，完全可以对二维dp进行压缩，压缩完就是下面所呈现的，完全背包的套路问题了。

此题务必要注意初始化问题。也正是因为优化了，所以在优化后的dp中，没有了

原因很简单，我们看上面的dp table可以看出，压缩成一维，这个部分完全就是没有必要的，只有是二维的时候才是有必要的。

 

不论是完全背包还是01背包，都强调，如果要求满载的情况，部分初值要设置为无效内容，何为无效，正负无穷，何时为正何时为

负，完全看dp状态方程是max和min，base case设置为无效状态，本意就是在比大小选择的时候，绝对不能选择这个初值，秉承着

这种思想和对base case的理解，才是真的理解了背包问题的模板。

 

此零钱问题就是很好的一个入门题。

 

 动态规划问题很灵活，套用模板是在理解模板的基础上，而不是单纯的使用

 

问题转化为：

有背包一个，承重为amount，（给的硬币随便选择）

现在要求从这些物品中挑选出总重量改好等于amount的物品

所有方案中使用硬币最少的情况

动态规划的模板大致都是一样的，但是根据题意，状态方程还是有差别的，此题，初始化和状态方程是需要注意的地方

题中明确说明，每次必须装满，满载情况的初始化，处理dp[0]，其他全部必须是无效值，那么这个无效值就根据题目的要求自行调整。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int size = coins.size();
        if(size == 0) return -1;
        vector<int> dp(amount+1,amount+1);//要求必须满载，也就是金额必须凑满，除了0，其余在此题求最小值的情况下，设置为正无穷，也就是不可能取到的amount+1（都是1块，也要amount个）
        dp[0] = 0;
        for(int i = 1;i<=size;++i)//外循环遍历硬币
        {
            for(int j = 1;j<=amount;++j)//内循环不断测试各种金额情况下，最小的凑齐方式
            {
                if(j>=coins[i-1])
                dp[j] = min(dp[j],dp[j-coins[i-1]]+1);
            }
        }
        return (dp[amount] == amount+1)?-1:dp[amount];
 
    }
};

 

518. 零钱兑换 II

https://leetcode-cn.com/problems/coin-change-2/

此题务必要注意初始化问题。

问题转化为：

有背包一个，承重为amount，（给的硬币随便选择）

现在要求从这些物品中挑选出总重量改好等于amount的物品

的方案个数。

 那么关于初始化问题，如果金额为零，一种方案，就是什么都不拿

因为要求要满载，所以其余变量初始化就是0，没人方案可以提供，全部处于失效状态。

不使用模板：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //不使用模板
        int size = coins.size();
        vector<vector<int>> dp(size+1,vector<int>(amount+1,0));
        //从前i个硬币中拿，组成金额为j的组合数
        //base case
        for(int i = 0;i<=coins.size();++i) dp[i][0] = 1;
        for(int i = 1;i<=coins.size();++i)
        {
            for(int j = 1;j<=amount;++j)
            {
                if(j-coins[i-1]>=0)
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                //不拿，前i-1组成金额j，拿，因为可以无限拿，前i个组成金额j-coins[i]的组合
                else 
                dp[i][j] = dp[i-1][j];
            }
        }
        return dp[size][amount];
    }
};

使用模板：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int size = coins.size();
        vector<int> dp(amount+1,0);
        dp[0] = 1;
        for(int i = 1;i<=size;++i)
        {
            for(int j = 1;j<=amount;++j)
            {
                if(j-coins[i-1]>=0)
                dp[j] = dp[j]+dp[j-coins[i-1]];
            }
        } 
        return dp[amount];
 
    }
};

leetcode官方配图对整个过程进行了详细的说明 

https://leetcode-cn.com/problems/coin-change-2/solution/ling-qian-dui-huan-ii-by-leetcode/ 

推荐答案（使用了完全背包的三种形式就行解答）：https://leetcode-cn.com/problems/coin-change-2/solution/bei-bao-si-xiang-jie-jue-ling-qian-dui-huan-wen-ti/

 

如果考虑到组合的顺序问题：377. 组合总和 Ⅳ

https://leetcode-cn.com/problems/combination-sum-iv/

推荐答案：https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int size = nums.size();
        vector<unsigned int>dp(target+1,0);
        dp[0] = 1;
        for(int i = 1;i<=target;++i)
        {
            for(int j = 1;j<=size;++j)
            {
                if(i-nums[j-1]>=0)
                dp[i] = dp[i]+dp[i-nums[j-1]];
            }
        }
        return dp[target];
 
    }
};

此题难点在于，考虑组合情况，解法方法很简单，内外循环颠倒即可，下面我们看看不同的内容循环有什么样的差别 

(来源：https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/)

target是外循环的情况： 

 如果target是外循环，那么整个循环的过程中，是一列一列算的，会考虑排列组合的情况

target是内循环的情况： 

如果target是内循环，那么整个循环的过程中，是一行一行算的，是不会考虑排列组合的情况

 

从上面两个表格也可以看出来，问题出在target为3，选择第一个物品的情况。

dp[3] = dp[3] + dp[3-1] ;之所以两种方法计算结果有差异，是因为第一个表中，dp[2]此时等于2;第二个表中，dp[2]此时等于 1;

其余完全背包问题

经过了上面几道题的历练，下面的这些题目就显得单薄了。

70. 爬楼梯 https://leetcode-cn.com/problems/climbing-stairs/