目录
题目链接：3. 完全背包问题 - AcWing题库
题目描述
有 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题目解析
在循环到第 i 件物品时，我们可分为不选，选1,2，……，k-1，k个，此时k * v [ i ] <= j ，所以我们只需在01背包的基础上再加一层循环即可 。
原本的状态转移方程是f [ i , j ] = max( f [ i - 1 , j ] , f [ i - 1 , j - v [ i ] ] + w [ i ] , f [ i - 1 , j - k * v [ i ] ] + k * w [ i ] )
而由上图可以看出 f [ i , j ] = max( f [ i - 1 , j ] , f [ i , j - v [ i ] ] ),这是由数学替换得到的公式，我们也可以直接理解，因为有无限个物品，我们在划分集合时可以划分为选择这种物品或者不选择这种物品，不选时为f [ i - 1 , j ] ，但是选择时由于有无限个，所以我们应该在f [ i , j - v [ i ] ] 的基础上进行更新，因为在此之前可能最优解已经选过了很多这种物品，如果再用01背包中的 f [ i - 1 , j - v [ i ] ],这个式子的意思是我们只会选择一种这种物品，但其实由无限个可以拿，所以应该在上一次拿过的基础上再拿。
代码
朴素版本
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int f[N][N],v[N],w[N];
int V,n;
int main()
{
cin>>n>>V;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=V;j++){
f[i][j]=f[i-1][j];
if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
}
cout<<f[n][V]<<endl;
return 0;
}优化版本
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e4+10;
int f[N],v[N],w[N];
int V,n;
int main()
{
cin>>n>>V;
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<=V;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
cout<<f[V]<<endl;
return 0;
}朴素版本和优化版本的区别
1.优化版本中体积的循环只能从小向大，而朴素版本的体积循环都可以；
2.朴素版本的体积循环一定要从零开始（假设从小到大），但是优化版本可只从v [ i ] 开始即可。