目录
前言：
在上一篇博客中我们已经初步了解了背包问题的实质（递推算法），并且已经解决了一个相对基础的问题：01背包
那么背包问题是否真的只是如此简单呢？
Absolutely，it's not！
那么，今天我来向大家介绍另一个问题——完全背包
ps:01背包请见:背包九讲之递推算法 一（01背包）_带着点诗意走吧的博客-CSDN博客
原问题见 :3. 完全背包问题 - AcWing题库
完全背包与01背包的区别
01背包：
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
完全背包：
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
但换汤不换药，总归算法核心思路相同 。
还说什么呢，搞起！
1.从01背包基础上分析完全背包
很显然，当每种物品都有无限件可用时，次数变得没有限制，使得单纯的穷举循环已经达不到目的了。
//01背包
#include <iostream>
using namespace std;
int v[1005];
int w[1005];
int f[1005][1005];
int main()
{
int n, m,i,j;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (i = 1; i <= n; i++)//判断n次
for (j = 1; j <= m; j++)//遍历使用1—m个空间,判断可否存放该次i
if (j < v[i])//该空间大小放不下
f[i][j] = f[i - 1][j];//等于上一次能放下的情况
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//选出上次与这次的大值：f[i-1][j-v[i]]+w[i]存放i剩的空间能放的最大值+本次值
printf("%d", f[n][m]);
}
如果想达到我们的要求，这段代码该如何进行改动呢？
我们自然先采用最朴素的暴力写法：
每种物品都有无数个，我们索性就在进行存放物体时再添加循环
1. for (j = 1; j <= m; j++)//遍历使用1—m个空间,判断可否存放该次i
2.for (j = 1; j <= m; j++)//遍历使用1—m个空间,判断可否存放该次i
for(k=1;k*v[i]<=j;k++)//列举使用k次的情况直至空间放不下
代码如下：
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1 ; i <= n ;i ++)
{
scanf("%d%d",&v[i],&w[i]);
}
for(int i = 1 ; i<=n ;i++)
for(int j = 0 ; j<=m ;j++)
{
for(int k = 0 ; k*v[i]<=j ; k++)
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
printf("%d",f[n][m]);
}但这种方法使用了三层循环，时间复杂度太高，很容易会出现超时的情况
如何优化呢？
是否可以去掉一层循环？
这就需要我们解决一个问题：
递推关系该如何分析
2.递推关系的分析与确定
在进行max取出决策的最大值时，由于k的大小不确定
于是我们列举其内部关系
01背包 ：max（f [ i-1 ][ j ] ,f[i-1][j-v[i]]）
变成了
max(f [ i-1 ][ j ] , f[ i-1 ][ j-1*v[ i ]]+1*w[ i ] ,f[ i-1 ][ j-2*v[ i ]]+2*w[ i ],...f[ i-1 ][ j-k*v[ i ]]+k*w[ i ])
很多小伙伴到这里就突然出现了大大的问号。
我去，这不定数目的比较咋写？
但只要你发挥你敏锐的什么？（洞察力）
就会发现：
1. f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
2. f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
当不看1式的第一项，2式每项正好比上一项少个w (这里的 v[i],w[i] 简写了)
则由上两式，可得出如下递推关系：
f[ i ][ j ]=max(f[ i,j-v ]+ w , f[ i-1 ][ j ] )
好家伙，递推关系与k无关了！
那我们索性把k循环去掉：
for(int i = 1 ; i <=n ;i++)
for(int j = 0 ; j <=m ;j++)
{
f[i][j] = f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}这个代码和01背包的非优化写法很像
我们参考01背包的优化方法
—— 二维转一维！
进一步优化
for(int i = 1 ; i<=n ;i++)
for(int j = v[i] ; j<=m ;j++）
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
ps:需要注意的是，这里的j是从小到大枚举，和01背包不一样
因为优化前是f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i])，比较的是同层的f:f[i],f[i]（而01背包是与前一层的f 进行比较即 f [i] 与 f [i-1] ）,所以j就不需要逆序了
3.完整写法
综上所述，完全背包的完整写法如下：
#include <iostream>
using namespace std;
int v[1005];
int w[1005];
int f[1005];
int main()
{
int n, m,i,j;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for (i = 1; i <= n; i++)//判断n次
for (j = v[i]; j <= m; j++)//遍历使用1—m个空间,判断可否只有i>v[i]进循环
f[j] = max(f[j], f[j - v[i]] + w[i]);
printf("%d", f[m]);
} 总结
完全背包的问题仍然是属于一个相对简单的问题，站在01背包代码的基础上，就能快速地找到二者相同之处。我们在日常学习的过程中也要拥有举一反三的能力与想法！
思考：如果，完全背包并不是物品无限个，而是有限个s呢？——多重背包问题 I
下一篇讲！
ps:核心代码进一步还可以优化为：边输入边计算
见上篇文章：背包九讲之递推算法 一（01背包）_带着点诗意走吧的博客-CSDN博客
作者水平有限，望海涵与指正。