01背包、完全背包问题几种变式总结，以及多重背包、组合背包模板

本文主要是介绍01背包、完全背包问题几种变式总结，以及多重背包、组合背包模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.求有多少种方法能恰好装满背包

1.1装满背包的方法——按排列计算还是按组合计算？

2.最值问题——最少需要几枚硬币,货物的最大价值

2.1最少需要几枚硬币

2.1.1 memset用法注意

3.二维01背包问题

4.多重背包问题

4.1优化前

4.2二进制优化

1.求有多少种方法能恰好装满背包

这种情况下我们一般令dp[ j ]的含义为：装满容量为 j 的背包的方法有dp[ j ]种。

因此这种情况的公式都是：dp[ j ] += dp[ j-nums[ i ] ]

1.1装满背包的方法——按排列计算还是按组合计算？

组合与顺序无关，只在乎元素，比如[1,2]和[2,1]是同一个组合；排列与顺序有关，所以[1,2]和[2,1]不是同一个组合。

在解决背包问题时，我们有内外两层循环：

在计算组合方法数时，外层循环依次是每一个元素，内层循环是遍历一整个背包；

在计算排列方法数时，外层循环依次是每个容量下的背包，内层循环是遍历所有元素。

因为对于计算排列来说：如果外层循环依次遍历每一个元素，那么背包里记录的数据，一定是先记录的nums[ 0 ]，再记录的nums[ 1 ]，不会出现反过来的情况，也就是只存在[ 1,2 ]不存在[ 2, 1 ]，自然而然得到的结果是按组合总数得到的。

而如果外层循环依次是每个容量下的背包，内层循环遍历所有元素，则如果有两个物品，物品一重量为1，物品二重量为2，则当背包容量为3时，会出现dp[3]=dp[1]+物品二value和dp[3]=dp[2]+物品一value这两种情况（dp[i]表示背包容量为i的最大价值）

计算排列的原理个人觉得比较难理解，但是我们可以通过一点数学的方法来推导整个过程。这里引用LeetCode.377题目的一条评论：

组合例题：LeetCode.518.零钱兑换II

class Solution {
public:int change(int amount, vector<int>& coins) {int dp[5005]={0};//dp[j]表示，如果确定有一个元素coins[i],那么有dp[j]种组合数凑成jdp[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];}
};

排列例题：LeetCode.377.组合总和IV

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int dp[1005]={0};int MAX = 0x7fffffff;dp[0] = 1;for(int i=1;i<=target;++i){for(int j=0;j<nums.size();++j){if(i-nums[j]>=0&&dp[i]<MAX-dp[i-nums[j]])
//这里的两个判断条件，前一个必写，后一个视题目数据量大小而定dp[i] += dp[i-nums[j]];}}return dp[target];}
};

2.最值问题——最少需要几枚硬币,货物的最大价值

2.1最少需要几枚硬币

LeetCode.322.零钱兑换

先考虑外层循环依次是背包的容量(需要凑成的总面值)，内层循环依次遍历所有面值的硬币的方法。

首先将原问题分解成子问题：

例如需要凑成 7 块钱，有[1,2,5]三种面值的硬币，求最少的硬币数dp[7]，它的子问题是：

（1）需要凑成 7-1=6 块钱，有[1,2,5]三种面值的硬币，求最少的硬币数dp[6]+1；

（2）需要凑成 7-2=5 块钱，有[1,2,5]三种面值的硬币，求最少的硬币数dp[5]+1；

（3）需要凑成 7-5=2 块钱，有[1,2,5]三种面值的硬币，求最少的硬币数dp[2]+1；

而要求dp[7]最小，因此dp[7]要取min{ dp[6]+1，dp[5]+1，dp[2]+1 }，得到状态方程如下：

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

其中 i 表示当前背包的容量

然后就像1.1中例题377组合总数一样，一直递推下去，这样只要直到dp[0](视具体题目进行初始化)，就能知道dp[7]的值。由于计算dp[7]时，dp[6]，dp[5]，dp[2]必须已知，所以从dp[1]开始计算。（视具体初始化情况而定，已经初始化了的元素就没必要再计算一遍了）

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int dp[10005];//dp[i]表示凑成 i 块钱最少需要几枚硬币memset(dp,0x7f,sizeof(dp));dp[0] = 0;int len = coins.size();for(int i=1;i<=amount;++i){for(int j=0;j<len;++j){if(i-coins[j]>=0)dp[i]=min(dp[i],dp[i-coins[j]]+1);}}return dp[amount]==0x7f7f7f7f?-1:dp[amount];}
};

从理解的角度，上面的代码比较容易理解，在理解了之后我们可以更换顺序来做，这样会更快：

class Solution {
public:int coinChange(vector<int>& coins, int amount) {int dp[10001];memset(dp,0x7f,sizeof(dp));dp[0] = 0;int len=coins.size();for(int j=0;j<len;++j){for(int i=coins[j];i<=amount;++i){
//快在这里的 i 可以从coins[j]开始dp[i] = min(dp[i],dp[i-coins[j]]+1);}}return dp[amount]==0x7f7f7f7f?-1:dp[amount];}
};

2.1.1 memset用法注意

首先是格式，对数组 a 初始化，格式为：memset( a,x,sizeof(a) )，其中 x 是想要初始化为的数。一般我们取最大值、1、0、-1等。

取“最大值”的方法：memset( a,0x7f,sizeof(a) )，而且这样初始化之后，一个int能达到的值并不是MAX_INT，因为此时一个int为：0x7f7f7f7f，而非0x7fffffff。

原因是：memset是对每1个字节（每8个二进制位）进行初始化。

3.二维01背包问题

LeetCode.474.一和零

也就是同时存在两个01背包，一个背包装0，容量是m；另一个背包装1，容量是n。

在之前做01背包问题一维优化的时候，我们提到内层循环中，背包应从最大容量开始逆序遍历，将这个问题转为二维也是一样的（因为如果从0开始遍历，则会覆盖掉前面存入的数据，最后结果就错了），我们定义dp[ i ][ j ]意为m=i，n=j时背包能装下的最大容量。

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {int dp[105][105]={0};//dp[i][j]意为有 i 个0，j 个1的情况下，最大子集中元素个数int len = strs.size();for(int k=0;k<len;++k){int cnt0=0,cnt1=0;for(char c : strs[k]){if(c == '0') ++cnt0; else ++cnt1;}for(int i=m;i>=cnt0;--i){for(int j=n;j>=cnt1;--j){dp[i][j] = max(dp[i-cnt0][j-cnt1]+1,dp[i][j]);}}}return dp[m][n];}
};

这里需要注意将计算0、1的个数的循环放在dp循环里一起算，这样就不用专门开两个数组cnt1[ ]和cnt0[ ]用来保存每个字符串中0、1的数量，而且也免去了多余的两层for循环计算。

4.多重背包问题

4.1优化前

由于数据范围比较小，O(N^3)=O(100^3) 也可以不超时，可以先从暴力解法入手，作为过渡。

需要注意的点：

（1）由于每种物品是有规定其能取的上限的，因此需要在之前01背包（而非完全背包，具体原因在第二点）的基础上，再引入一个循环用于遍历某个物品 取0个、取1个……取s个的所有情况。

（2）一维优化后的01背包中，内层循环需要逆序，而一维优化的完全背包中，内层循环无需逆序。在多重背包问题中，内层循环依旧需要逆序，这也是为什么说它是建立在01背包的基础上的。可以理解为，01背包和多重背包都是某种物品取有限个，而完全背包允许某个物品取无穷多个，只要背包装得下。

#include<iostream>
using namespace std;int n,m;
int dp[110]={0};int main()
{cin>>n>>m;for(int i=0;i<n;++i){int v,w,s;cin>>v>>w>>s;for(int j=m;j>=1;--j)for(int k=0;k<=s&&v*k<=j;++k)dp[j] = max(dp[j],dp[j-v*k]+w*k);}cout<<dp[m];return 0;
}

4.2二进制优化

这道题是多重背包 I 在数据上的加强。数据量决定了用优化前的做法极大概率会超时。

前面说了，多重背包问题实际上是建立在01背包问题的基础上的，那么我们可以考虑将多重背包再化为01背包（比如一种物品有10件，那就把它当成十件种类不同，但是重量和价值都一样的物品，这样每件物品只能取一次，也就是01背包问题），这样复杂度就能向01背包靠拢了。

可惜如果只是简单的转化，也是一个O(N^3)的过程。

由此引出了二进制优化的方法。能将原来每件商品的件数 Si 减少到logSi。

#include<iostream>
using namespace std;int n,m,cnt=0;
int dp[2200]={0};
int w[22000];
int v[22000];int main()
{cin>>n>>m;//以下先进行二进制优化过程for(int i=0;i<n;++i){int a,b,s;cin>>a>>b>>s;
//每次进行while循环之前记得把k初始化为 1int k=1;
//着重注意下面这个while循环的写法while(k<=s){cnt++;w[cnt]=k*a;v[cnt]=k*b;s-=k;k*=2;}if(s>0){cnt++;w[cnt]=a*s;v[cnt]=b*s;}}
//cnt实际上记录的是二进制优化过后，01背包中商品的总件数n=cnt;//以下进行01背包过程for(int i=1;i<=n;++i){for(int j=m;j>=w[i];--j){dp[j] = max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m];return 0;
}

5.组合背包问题

组合背包没有很好的解题方法，只能用三重循环来做，但是其中也有一些注意事项。

#include<iostream>
using namespace std;int N,V;
int dp[110],val[110],wei[110];int main()
{cin>>N>>V;for(int i=0;i<N;++i){int s;cin>>s;for(int j=0;j<s;++j) cin>>wei[j]>>val[j];for(int j=V;j>0;--j)for(int k=0;k<s;++k)if(j>=wei[k])dp[j]=max(dp[j],dp[j-wei[k]]+val[k]);}cout<<dp[V];return 0;
}

第三重循环中的写法需要特别注意。

一开始我写的是这样：