[数据结构与算法] 01背包输出路径、完全背包、多重背包

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 01背包输出路径、完全背包、多重背包 -> 正文阅读

[数据结构与算法]01背包输出路径、完全背包、多重背包

背包问题

一、01 Knapsack（输出路径- >选的物品)

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
const int N=105;
int w[N];
int v[N];
int path[N][1005];//path[i][j] 1
int dp[1005]; 
//dp[i][j]代表有i件商品可供选择有j这么大的容量可供盛放 这时可取得的最大商品价值 
int main(){ 
	int n,m;//商品件数和背包容量 ,要取得最大的价值 
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			path[i][j]=0;	
//			dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
			if(dp[j-w[i]]+v[i]>dp[j]){
				path[i][j]=1;
				dp[j]=dp[j-w[i]]+v[i];
			}
		} 
	} 
//	cout<<dp[m]<<endl;
	stack<int> st;
	int i=n;
	int j=m;
	while(i>0&&j>0){
		if(path[i][j]==1){	
			st.push(i);
		j-=w[i];
		}
		i--;
	}
	while(!st.empty()){
		cout<<st.top()<<endl;
		st.pop();
	}
	return 0;
}

动态规划的核心思想避免重复计算在01背包问题中体现得淋漓尽致。第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值决定，暴力枚举忽略了这个事实。

二、完全背包

在这里插入图片描述

1、三重循环，极可能TLE，滚动数组优化后j逆向枚举

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
//			if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
//			else dp[i][j]=dp[i-1][j];
			for(int k=0;k*w[i]<=j;k++){
				dp[i][j]=max(dp[i][j],dp[i-1][j-k*w[i]]+k*v[i]);
			}
		}
	}

(如果这种三重循环暴力的方法不超时，且欲将其优化成一维数组，枚举j时要像0-1背包一样逆向噢，因为状态转移方程max第二项是 $d p 【 i ? 1 】$
在这里插入图片描述

2、二重，优化消去变量k（没有特别厘清，但可以直接从完全背包角度理解，取完一个还可以取无数个）

a.不装入第i种物品，即 $d p [i ? 1] [j]$ ，同01背包；
b.装入第i种物品，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到 $d p [i ? 1] [j ? w [i]]$ 而应该转移到 $d p [i] [j ? w [i]]$ ，即装入第 $i$ 种商品后还可以再继续装入第 $i$ 种商品。

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j>=w[i])dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}

或者

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			if(j>=w[i])dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
		}
	}

这个状态转移方程与01背包问题唯一不同就是max第二项不是dp[i-1]而是dp[i]。

3、滚动数组优化成一维数组，j正向枚举

和01背包问题类似，也可进行空间优化，优化后不同点在于这里的 j 只能正向枚举而01背包只能逆向枚举，因为这里的max第二项是dp[i]而01背包是dp[i-1]，即这里就是需要覆盖而01背包需要避免覆盖。


	for(int i=1;i<=n;i++){
		for(int j=w[i];j<=m;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	} 
	cout<<dp[m];

}

01背包和完全背包问题此解法的空间优化版解法唯一不同就是前者的 j 只能逆向枚举而后者的 j 只能正向枚举，这是由二者的状态转移方程决定的
在这里插入图片描述

三、背包恰好装满的情形

为什么 $d p [m]$ 是能取到得最大价值，因为一开始对dp数组进行初始化时，将dp数组所有元素都初始化为0了， $d p [m]$ 可能并非由 $d p [0]$ 这个状态庄毅而来，可能是由中途某个 $d p [k]$ 转移而来

如果问，恰好占用了m这么多的背包容量这一条件下能取得得最大价值，就在初始化dp数组时，将dp【0】初始化为0，其余都初始化为负无穷
在这里插入图片描述

解释二则：

现在考虑动态规划的初始值问题。
在之前的问题中，dp[i][v]初始化设置为0.
因为在初始状态，背包中没有任何物品。不论背包的容量多大，里面的价值只是0.这个状态是合法的。因为背包并没有超出容量。
现在，背包只有完全占满才是合法的值。那么在初始状态，dp[i][0]=0是合法的，因为容量为0，不放任何东西就是合法了。其他的都是非法值。应该设置为负无穷。
背包问题有时候还有一个限制就是必须恰好装满背包，此时基本思路没有区别，只是在初始化的时候有所不同。

如果没有恰好装满背包的限制，我们将dp全部初始化成0就可以了。因为任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。如果有恰好装满的限制，那只应该将dp[0,…,N][0]初始为0，其它dp值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。

？为什么不能初始化为0，让0和背包装满时的dp正数值进行区分呢？

由以上图表可见，dp数组的值 $d p 【 i 】【 j 】$ 表示的含义是对于前i件商品，能否装满容量为j的背包，能装满的话 $d p 【 i 】【 j 】$ 表示装满时的最大价值。
何以确保装满了容量为j的背包，因为递推的过程其实是由取一件商品算出对应容量的背包，从而为dp[i]【该若干商品体积】赋予一个正的价值，那么未进行赋值的对应容量的背包自然就是不能被这些商品装满的
那么，为什么不干脆就初始化未0，从而与能被装满的背包价值来区分呢？
是因为一开始赋予一个不合法的值更符合意义（0对于容量未0的背包也是合法的）嘛？

参考链接

四、多重背包问题Ⅰ（数据小，拆成0-1背包）

在这里插入图片描述

1、将多重背包一个一个拆出来，拆成0—1背包

将多重背包拆成0—1背包要注意的是这时数组最大容量不能由商品种类数决定，而是总建树=种类*件数

#include <iostream>
using namespace std;
const int N=1e5;//这时数组最大容量不能由商品种类数决定，而是总建树=种类*件数 
int v[N];//价值 
int w[N];//重量 
int dp[N]; 
int main(){
	int n,m;
	cin>>n>>m;
	int vv,ww,c;
	int cnt=1;//算作0-1背包的商品总建树 
	for(int i=1;i<=n;i++){
//		cin>>w[i]>>v[i];
		cin>>ww>>vv>>c;
		for(int j=1;j<=c;j++){
			v[cnt]=vv;
			w[cnt]=ww;	
			cnt++;
		}
	}
	for(int i=1;i<=cnt;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;
}

2、直接加一层循环，枚举每件商品的件数

三重循环的层次不能变，可能跟滚动数组中那种求值顺序有关？×
显然是因为逻辑不对，第i件物品装入或者不装入而获得的最大价值完全可以由前面i-1件物品的最大价值和背包剩余容量决定，容量要作为选取的先决条件，必定在选取件数的外层呀

#include <iostream>
using namespace std;
const int N=1e5;//这时数组最大容量不能由商品种类数决定，而是总建树=种类*件数 
int v[N];//价值 
int w[N];//重量 
int s[N];//每种商品的建树 
int dp[N]; 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i]>>s[i];
	}

	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--){
			for(int k=1;k<=s[i]&&k*w[i]<=j;k++){
				dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int k=1;k<=s[i];k++){
//			for(int j=m;j>=w[i];j--){
//				if(k*w[i]<=j)dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
//			}
//		}
//	}
	cout<<dp[m];
    return 0;
}

五、多重背包问题Ⅱ(二进制优化划分）

数据范围增大，三重循环会超时
在这里插入图片描述
对于任意一个数字来说，都可以用一个二进制来表达，如7 ，二进制为“111”，可以被划分为个数分别为1、2和4的三堆物品，但我们此时并不是完全采用二进制来划分.

给定一个数s，问最少可以把s分成多少个数，并把这些数拼成小于等于s的所有的数？
$log_2S$ (+1)个
并非把物体分成S份，而是分成 $log_2S$ 份
S
1、2、4、8……x
x=S-1-2-4-8-……
一秒可以执行 $10^7$ 以内这个复杂度的操作
除了这些以2为底的幂次数，最后剩余的非零数也要算在组成数之中

以 9 为例，先划分出一个1，再划分出 2，再划分出 4，最后剩下了一个 2，2小于8，就需要单独划分为一堆。

采用二进制思路将第 i 种物品分成 $O(logS_i)$ 件物品，将原问题转化为了复杂度为
在这里插入图片描述

的 01 背包问题

#include <iostream>
#include <vector>
using namespace std;
const int N=1e5;
int v[N];//价值 
int w[N];//重量 
int dp[N]; 
struct node{
	int w;
	int v;
	node(int w,int v):w(w),v(v){};
}; 
int main(){
	int n,m;
	cin>>n>>m;
	int ww,vv,s;
	vector<node> good;
	for(int i=1;i<=n;i++){
	//一个一个拆成0-1背包 ，N`=N*s,N`*v会超时
//	有这么几个数，每个数选或不选，一定能用这几个数拼出x 
		cin>>ww>>vv>>s;
		for(int k=1;k<=s;k*=2){//这s件不拆成1、1、1、1，而是1，2，4， 
			s-=k;
			good.push_back(node(k*ww,k*vv));
		}
		if(s>0)good.push_back(node(s*ww,s*vv));
	}
	int len=good.size();
	for(int i=0;i<len;i++){
		for(int j=m;j>=good[i].w;j--){
			dp[j]=max(dp[j],dp[j-good[i].w]+good[i].v);
		}
	}
	cout<<dp[m];
    return 0;
}

六、二维背包（有两个对于背包的限制，不止容量还有体积啥的）

前面讨论的背包容量都是一个量：重量。二维背包问题是指每个背包有两个限制条件（比如重量和体积限制），选择物品必须要满足这两个条件。此类问题的解法和一维背包问题不同就是dp数组要多开一维，其他和一维背包完全一样

题目们

474. 一和零

题目链接
在这里插入图片描述
这里的一和零是字符呀TT，不要再拿字符串的元素去和整数作比较了
二维背包

int findMaxForm(vector<string>& strs, int m, int n) {
//	int w1[N];//限制1，0 的个数,<=m
//	int w2[N];//限制2，1 的个数,<=n
	int dp[m+1][n+1];
	for(int i=0;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=0;
		}
	}
	// vector<vector<int> > dp(m+1,vector<int> (n+1,0));
	int w1,w2;
	int len=strs.size();
	for(int i=0;i<len;i++){
		w1=w2=0;
        int s=strs[i].size();
		for(int x=0;x<s;x++){
			if(strs[i][x]=='0')w1++;
			else if(strs[i][x]=='1')w2++;
		}
		for(int j=m;j>=w1;j--){
			for(int k=n;k>=w2;k--){
				dp[j][k]=max(dp[j][k],dp[j-w1][k-w2]+1);
			}
		}
	} 
	return dp[m][n];
}

416. Partition Equal Subset Sum

题目链接
在这里插入图片描述
题意：从所有元素中取出若干是否能恰好装满sum/2容量的背包
恰好装满型，零一背包（或者说是多重背包拆成0-1背包）

一个正整数数组是否可以划分为两个元素之和相等的子集
哈哈哈哈哈哈哈哈哈哈这题搞懂 背包恰好装满情形

可以回答为什么初始化dp数组为负无穷而不是-1甚至0了

上面提出疑问时就说了，既然得到某个容量背包的价值时首先对该容量的确定，是取若干个商品的组合（取几个商品的体积之和S，对应的容量为S的背包自然可以被装满），当然了，这个取几个商品组合的过程是通过有条件的递推，什么条件呢？就是要从 能被装满的背包的价值 的基础上，遍历后来的商品，取或不取

就是相当于， $状态 d p [j] 由状态 d p [j ? n u m [i ? 1]]$ 推出来，那么 $d p [j ? n u m [i ? 1]]$ 这个状态就要是存在的，有意义的
而这里的有意义，指的就是 $d p [j ? n u m [i ? 1]]$ 对应的是若干件商品组合而成的能装满的对应容量的背包的价值

这里对dp数组没有意义的值设置为负无穷，是为了在执行状态状态转移方程时，

dp[j]=max(dp[j],dp[j-num[i-1]]+1);

方便判断dp[j-num[i-1]]是否对应的是能被装满的背包，只有先满足这个条件，才有资格去与dp[j]进行大小比较

而对初始没有意义的值初始化为负无穷，就可以借助方程中天然的max函数（本来是判断第二个条件的）来筛掉不满足第一个条件的状态
当然了，不初始化为负无穷而是初始化为-1，也可以，但是就得先单独判断第一个条件（否则的话，max(dp[j],dp[j-nums[i-1]]+1)的比较，谁大谁小就说不定了，因为后者带了个后缀呀）

if(dp[j-nums[i-1]]!=-1)dp[j]=max(dp[j],dp[j-nums[i-1]]+1);

1、初始化为-1

bool canPartition(vector<int>& nums) {
        vector<int> dp(10005,-1);//dp数组范围是背包最大容量噢，sum/2
		dp[0]=0;
		int n=nums.size();
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=nums[i];
		}
    if(sum%2!=0)return false;
		for(int i=1;i<=n;i++){
			for(int j=sum/2;j>=nums[i-1];j--){
//nums数组从0存储，但i必须从1开始遍历，
//因为dp数组，dp【0】代表一件商品都不选而非选第0件 
				if(dp[j-nums[i-1]]!=-1)dp[j]=max(dp[j],dp[j-nums[i-1]]+1); 
			}
		}
		if(dp[sum/2]>0)return true;//>=0也是能过的
		else return false;
}

if (dp[j - w[i]] != -1 && dp[j - w[i]] + v[i] >= dp[j])

2、初始化为负无穷（`max(dp[j],dp[j-nums[i-1]]+1)`，如果`dp[j-nums[i-1]]`是不存在的状态，只要`dp[j-nums[i-1]]+1`的值比0还小，自然可以被dp[j]（至少为0）比下去，要想不比较，至少初始化为-2， $? 2 + 1 < 0$

bool canPartition(vector<int>& nums) {
        vector<int> dp(10005,-2);//求的不是取多少个元素，只是是否可行
		dp[0]=0;
		int n=nums.size();
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=nums[i];
		}
    if(sum%2!=0)return false;
		for(int i=1;i<=n;i++){
			for(int j=sum/2;j>=nums[i-1];j--){
//nums数组从0存储，但i必须从1开始遍历，
//因为dp数组，dp【0】代表一件商品都不选而非选第0件 
				dp[j]=max(dp[j],dp[j-nums[i-1]]+1); 
			}
		}
		if(dp[sum/2]>0)return true;
		else return false;
}

3、初始化为false

//由于求的不是取多少个元素，只是是否可行

bool canPartition(vector<int>& nums) {
        vector<int> dp(10005,false);
		dp[0]=true;
		int n=nums.size();
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=nums[i];
		}
    if(sum%2!=0)return false;//1 2 3 5
		for(int i=1;i<=n;i++){
			for(int j=sum/2;j>=nums[i-1];j--){
//nums数组从0存储，但i必须从1开始遍历，
//因为dp数组，dp【0】代表一件商品都不选而非选第0件 
				// dp[j]=max(dp[j],dp[j-nums[i-1]]+1); 
                dp[j]=dp[j]||dp[j-nums[i-1]];
			}
		}
		if(dp[sum/2])return true;
		else return false;
}

4、bitset优化

bitset相当于bool数组，bool[sum]=1表示能得到各商品总和为sum的组合
用bitset来记录这些商品所有可能组合的和。

具体步骤是：开辟一个大小为5001的bisets（因为所有元素和不超过10000）名为bits，最后得到的bits满足bits[i]=1则代表nums中某些元素的和为i，最后判断bits[sum/2]是否为1即可

初始时bits[0] = 1，然后从前往后遍历nums数组，对于当前遍历到的数字num，把 bits 向左平移 num 位，然后再或上原来的 bits，这样就代表在原先的基础上又新增了一个和的可能性。比如对于数组 [1,3]，初始化 bits 为 …00001，遍历到1，bits 变为…00011，然后遍历到3，bits 变为了 …11011。最终得到的bit在第1,3,4位上为1，代表了可能的和为1,3,4，这样遍历完整个数组后，去看 bits[sum/2] 是否为1即可。

	00000000000001//初始bit[0]=1 
	00000000000010//左移1位 
--->00000000000011//包含了组合为0，1的可能 
	00000000001100//左移2位
--->00000000001111//包含了组合为0，1，2，3的可能
	00000001111000//左移3位
--->00000001111111//包含了组合为0，1，2，3,4,5,6的可能	
	00111111100000//左移5位
--->00111111111111//包含了0,1,2,3,4,5,6,7,8,9,10,11这所有的可能

其实也很好理解呀，bit=bit|(bit<<nums[i]);
前一个bit保留了上一次得到的所有组合结果，后一个bit<<nums[i],在上一次得到的每个结果的基础上加上nums[i]
取nums[i]的所有情况都包含在后者里，不取nums[i]的所有情况都包含在前者中
这实际上是个非常暴力的思想，但是借助位运算和bit非常巧妙的极大优化

bool canPartition(vector<int>& nums) {
		int n=nums.size();
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=nums[i];
		}
    	if(sum&1)return false;//sum奇数 
    	sum >>= 1;
    	bitset<10005> bit(1);//所有元素之和不会超过20000，一半就是10000
//    	相当于bit[0]=1啦
		for(int i=0;i<n;i++){
			bit=bit|(bit<<nums[i]);
		} 
		if(bit[sum])return true;
		else return false;
}

322. Coin Change

题目链接
在这里插入图片描述

在这里插入图片描述

$2^{31}$ 数量级也就是 $2 e 10$ ,脑子不清楚乍一看以为是什么惊天大数字，太差劲了,对于这个数字应该非常熟悉才是，int的数据范围嘛
int的取值范围为： $2^{31} ——2^{31}-1$ ，即-2147483648——2147483647
所以非常值得注意的是溢出风险（爆int）， dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
当然了这题没有，amount范围小，虽然是for(int j=coins[i-1];j<=amount;j++)正方向枚举，但是大于amount的coins[i]进不去循环，能进去的不会溢出

题意：每种物品（某种面值的硬币）有无数个，怎样取最少的物品放慢容量为amount的背包，面值看成商品重量，硬币个数看成价值（每个硬币价值为1），要得最少的价值啦
恰好装满型，完全背包

int coinChange(vector<int>& coins, int amount) {
		const int inf=0x3f3f3f;//要大于最小的，初始化为正无穷大 
		vector<int> dp(amount+1,inf);
		dp[0]=0; 
        int cnt=coins.size();
		for(int i=1;i<=cnt;i++){
			for(int j=coins[i-1];j<=amount;j++){//完全背包正着枚举噢 
				dp[j]=min(dp[j],dp[j-coins[i-1]]+1);
  // if(dp[j-coins[i-1]]+1<dp[j])dp[j]=dp[j-coins[i-1]];
   // if(dp[j-coins[i-1]]<dp[j]-1)dp[j]=dp[j-coins[i-1]];
			}
		} 
		if(dp[amount]==inf)return -1;
		else return dp[amount];
}

494. Target Sum

494. Target Sum
在这里插入图片描述
0-1背包，恰好装满型，不求价值的最值，求取法总和
比较巧妙地转化成了恰好装满背包的问题，主要因为问的是给所有数组元素赋予一些 $^{'} +^{'},^{'} ?^{'}$ 之后得到的式子的值是一个准确的值，而不是某个整数k的倍数（如果是这种，那么求得不是取法而是是否能取到）

int findTargetSumWays(vector<int>& nums, int target) {
//      正整数序列，带'+'的元素之和为A，带'-'的元素之和为B
//	  A+B=sum,A-B=target, A=(sum+target)/2 恰好装满型  
//	有几种装法，装满A
//0-1背包，恰好装满型，不求价值的最值，求取法总和 
	int cnt=nums.size();
	int sum=0;
	for(int i=0;i<cnt;i++){
		sum+=nums[i];
	} 
	if((sum+target)<0||target>sum)return 0;
	//有一个样例就是[100],-200 
	if((sum+target)&1)return 0;
	int A=(sum+target)>>1;
	vector<int> dp(1005,0);
	dp[0]=1;
	for(int i=1;i<=cnt;i++){
		for(int j=A;j>=nums[i-1];j--){
			dp[j]=dp[j]+dp[j-nums[i-1]];//取或不取，两种取法都要 
		} 
	}
	return dp[A]; 
}