完全背包问题呢，见名知意，就是所谓的物品无限多，选也选不完的那种，是多重背包的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; }
这里为了好理解写了朴素版本的多重背包，可以二进制优化和单调队列优化，具体可以看一下我上
一篇博客写的
这个枚举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
笔者本科大二在读，水平有限，一些地方写的不够详细或者理解的不准确，望各位大佬指出，共同进步。下篇更新混合背包问题。
