更好的阅读体验
题目描述：完全背包问题
有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi, wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
10
基本思考框架
C++ 代码
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
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 = 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]);
}
cout<<f[n][m]<<endl;
}
优化思路
我们列举一下更新次序的内部关系：
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 , .....)
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 , .....)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
有了上面的关系，那么其实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 = 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-1][j-v[i]]+w[i]);
}
两个代码其实只有一句不同（注意下标）
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
因为和01背包代码很相像，我们很容易想到进一步优化。核心代码可以改成下面这样
for(int i = 1 ; i<=n ;i++)
for(int j = v[i] ; j<=m ;j++)//注意了，这里的j是从小到大枚举，和01背包不一样
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
综上所述，完全背包的最终写法如下：
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
int n,m;
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++)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
}
额，那个图片是裂开了吗（逃还不懂背包问题的朋友们可以看看这篇博客，感觉很详细：https://blog.csdn.net/raelum/article/details/128996521
gitee开了图床防盗链,网页上显示不了，https://gitee.com/chzarles/images/raw/master/imgs/006eb5E0gy1g7yyd0jjcyj30wk0fpdhc.jpg
可以复制链接在浏览器打开图片
y总没有总结背包问题模板，需要模板的可以去看看这个博客： https://blog.csdn.net/m0_61654975/article/details/141210427
为什么优化前的代码是f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i])而不是max(f[i-1][j],f[i-1][j-v[i]]+w[i])
你这么写的想法是考虑第i个物品不取的情况吧，但是看三层循环的版本f[i][j] = max(f[i][j],f[i-1][j-kv[i]]+kw[i]);可以发现，k==0的时候就是不取第i个的情况，然后用这个值去不断更新f[i][j]。如果按你的写法，并不会每次把f[i][j]往大了更新，而是不确定的
谢谢大佬！我纠结了好久看到你的回复终于想通了。
可是按你的方程，第一个f[i][j]和f[i-1][j]比较你又怎么懂f[i][j]的数值是多少呢，f[i][j]不是按照前面的推断出数值的吗？
最初的是0
大佬跪了跪了 看懂这个之后豁然开朗www谢谢大佬
谢谢大佬！
初始条件下f[i][j]为0，所以在第一次max比较的时候肯定会被修改为一个值。而f[i-1][j]对应的是k==0的情况，也就是在k=0的时候第一次被修改的情况，如果初始设为f[i-1][j]的话，k可以从1开始。（其实我觉得都行hhh）
谢谢大佬
放第i件物品。这里的处理和01背包有所不同，因为01背包的每个物品只能选择一个，因此选择放第i件物品就意味着必须转移到dp[i-1][v-w[i]]这个状态；但是完全背包问题不同，完全背包如果选择放第i件物品之后并不是转移到dp[i-1][v-w[i]]这个状态；而是转移到dp[i][v-w[i]]，这是因为每种物品可以放任意件（注意有容量的限制，因此还是有限的），放了第i件物品后还可以继续放第i件物品，直到第二维的v-w[i]无法保持大于等于0为止。
非常清晰 orz
太牛了，终于懂了
可以分开考虑。
假设无法放置第
i个，那么dp[i][j] = dp[i - 1][j]假设可以放置第’i’个，那么
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i])（这里是要从’k = 0’开始取到dp[i][j]）的最大值当
k = 0时，第二种情况涵盖了，所以可以写在一起。我顶
如果是第一个的话，j起始应该是是0 吧
这样写是为了一直迭代更新，因为集合被分成了好几部分而不是像01背包那样只有两份
大佬 Orz
or2
佬
其实就是选不同个数物品之间的比较
初始化为零,值一定会被覆盖成别的数,然后别的数和他同一层比较
现在暴力版的过不了了。TLE
好详细啊，好久没有看到一篇这么清晰明了的题解了，膜拜膜拜
+1
为什么要取max（f[i][j]）呢 f[i][j] = max(f[i][j], f[j - v[i]] + w[i])
下边有大佬回复过
因为有可能我拿的不是最优解
这头像和id,6
神他妈yxc
大雪菜！
一个题解下面至少三个y总头像
拿到的这个不一定是最优的，你得取最大值
把k循环去掉后应该这样写吧！
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1 ; i<=n ;i){
int v,w;
cin>>v>>w;
for(int j =0 ; j<=m ;j)
{ if(j>=v){
f[i][j] = max(f[i-1][j],f[i][j-v]+w);
}
else{
f[i][j] = f[i-1][j];
}
}
}
cout<<f[n][m]<<endl;
}
差不多，应该多是可以的
有一个问题我想不明白，优化的时候，为什么要去考虑
f[i][j - v]呢，是怎么想到把这个的展开式和f[i][j]的展开式作比较的呢？同问
我感觉不对i做变化是为了方便下一步去掉i那一维度，所以对j进行j-v的变化
对于为什么最开始的代码是f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i])而不是max(f[i-1][j],f[i-1][j-v[i]]+w[i])，我的理解是f[i][j]是指当前第k个还没装的状态，也就是上一次状态，f[i-1][j-kv[i]]+kw[i]]是指在一个没装的情况下装了k个，比较的是第k个装不装
01背包：for(int i=1;i<=n;i) for(int j=m;j>=v[i];j–) f[j]=max(f[j],f[j-v[i]]+w[i]);
完全背包：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]);
有个问题，就是，问什么01背包问题在内存优化的时候
j需要从大到小遍历，而完全背包问题中的j就需要从小到大了注意，二者不同在于，完全背包是
f[i][j - v[i]] + w[i]，而0-1背包是f[i - 1][j - v[i]] + w[i]；若空间压缩成一维，对0-1背包，更新
f[i][j]需要的上一轮中的j - v[i]，对应i - 1而不是i，若j从小到大遍历，由于先计算j - v[i]再计算j，上一轮的值会被覆盖；但完全背包，更新
f[i][j]需要本轮的j - v[i]，对应i而不是i - 1；需要的正是本轮的值感谢感谢大佬！！！！！，听明白了
大佬流弊
for(int j = 0 ; j<=m ;j++) 这句代码 j可以从j=1开始吗？
我想了一下那个优化后的式子有什么表达含义，y总不是跟f[i][j - v]的式子展开作比较的嘛，我就想这意思有什么含义。完全背包的思想是把集合分成好几份，然后取最大值，而优化后的式子是这样的，f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])，那能不能像01背包那样思考呢，可以，可以想成分为两份，一份是不取第i个物品，另一份是至少取一个i物品，所以是【j-v】，然后再在前i个物品里面选，这里跟01背包的区别是还有可能取到第i个物品的，01背包是在前i-1个里面选，是不可能再选到第i个物品的。f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])表达的就是这么个意思
666
最后输出有点问题
$很棒$
为什么这压缩成一维的，会被报超时啊？？？
把k带进去为什么f[i][j]不应该等于max(f[i][j]， f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , .....)吗
那完全背包和01背包的一维写法是不是一样啊
遍历的顺序不一样~你看看上面大佬说的
01背包需要的是上一轮(i - 1)的值，如果从小到大枚举，那么上一轮的值就会被覆盖
而完全背包需要的是本轮的值，那么不会出现覆盖问题
为什么不需要初始化为负无穷呢