概述
每件物品可以选任意个
题解
1. 状态表示
集合:所有只考虑了前i个物品,且体积不大于j的所有选法
属性:Max
2. 状态计算
集合的划分
f[i,j]:0,1,2,…,k
第i个物品选多少个?k这里有体积进行限制
f[i-1,j]
曲线救国:
1. 去掉k个物品i
2. 求Max, f[i-1,j-kv[i]]
3. 再加回来k个物品i
f[i-1,j-kv[i]] + k*w[i].
f[i][j]=max(f[i][j], f[i-1][j-v[i]k]+kw[i]);
// 三重循环
3. 优化:
f[i,j] = Max(f[i-1,j], f[i-1,j-v]+w,f[i-1,j-2v]+2w,…)
f[i,j-v]=Max(f[i-1,j-v], f[i-1,j-2v]+w,…)
发现 f[i,v]=Max(f[i-1,j], f[i,j-v]+w);
代码
#include<iostream>
using namespace std;
const int N=1010;
int n,m;
int v[N], w[N];
int f[N];
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++)
f[j]=max(f[j], f[j-v[i]]+w[i]); // f[j-v[i]已经被算过,所以是一致的
cout<<f[m]<<endl;
return 0;
}