浅谈完全背包问题

完全背包问题呢，见名知意，就是所谓的物品无限多，选也选不完的那种，是多重背包的promax版本。完全背包问题是背包问题的一种变体，与0/1背包问题有所不同。在完全背包问题中，每种物品的数量是无限的，可以选择任意数量的某一种物品放入背包中。问题的描述如下： 给定一个背包容量为m，有n种物品，每种物品有重量v[i]和价值w[i]，且数量无限。目标是选择物品放入背包，使得它们的总重量不超过背包容量，并且总价值最大。 与0/1背包问题相比，完全背包问题的状态转移方程有所不同，因为每种物品可以选择多次。 解决完全背包问题的方法与0/1背包问题类似，可以使用动态规划、贪心算法等。常见的动态规划方法包括自底向上的迭代和自顶向下的递归+记忆化搜索。

既然是promax版本，那还是离不开01背包啊，既然我可以无限选，那就可以选到知道背包装不下为止，就是m/v[i]。

例题就用acwing上的完全背包问题：3. 完全背包问题 - AcWing题库​​​​​​

朴素版——枚举k

最先想到的就是简单的枚举k了吧，把完全背包转换成多重背包，每个物品最多枚举到m/v[i]，相当于每个物品的个数确定了。

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

这里为了好理解写了朴素版本的多重背包，可以二进制优化和单调队列优化，具体可以看一下我上

一篇博客写的细谈多重背包问题-CSDN博客

这个枚举k肯定过不了，时间复杂度太大，考虑优化

进阶版——dp正推（一维滚动数组）

#include<iostream>
using namespace std;
int dp[1005];//dp[i]表示背包容量为i是最大价值
int n,m;//n个物品m背包容量
int v[1005],w[1005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=v[i];j<=m;j++){//这里从v[i]到m，保证了能选1——m/v[i]（最多）
					dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//状态转移方程
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}

下面解释一下为啥要正序，因为不是正序的话从小到大更新，在更新大的时候状态可以从小的状态转移过来。

这样的话时间复杂度大大降低，优化掉了那层k循环，时间复杂度O（nm）

视频讲解这个B站有动画的笔者感觉挺好【信息学奥赛教程】完全背包问题_哔哩哔哩_bilibili

笔者本科大二在读，水平有限，一些地方写的不够详细或者理解的不准确，望各位大佬指出，共同进步。下篇更新混合背包问题。