完全背包问题呢，见名知意，就是所谓的物品无限多，选也选不完的那种，是多重背包的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]，相当于每个物品的个数确定了。
代码语言：javascript复制#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正推（一维滚动数组）
代码语言：javascript复制#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
笔者本科大二在读，水平有限，一些地方写的不够详细或者理解的不准确，望各位大佬指出，共同进步。下篇更新混合背包问题。
