概述
每件物品最多可以选k个
题解
f[i,j]
状态表示
集合:所有只从前i个物品中选,且总体积不超过j的选法
属性:最大值
状态计算
集合划分
第i个物品最多选多少个
f[i,j] = max(f[i-1,j-kv]+kw) k=0,1,2,…,s[i]
优化
f[i,j] = Max(f[i-1,j], f[i-1,j-v]+w,f[i-1,j-2v]+2w,…,f[i-1,j-sv]+sw)
f[i,j-v]=Max(f[i-1,j-v], f[i-1,j-2v]+w,…, f[i-1,j-(s+1)v]+(s+1)w)
进阶:二进制优化
代码
#include<iostream>
using namespace std;
const int N=110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++) // 100^3
for(int j=0;j<=m;j++)
for(int k=0;k<=s[i] && k*v[i]<=j;k++){
f[i][j]=max(f[i][j], f[i-1][j-v[i]*k]+w[i]*k);
}
cout<<f[n][m]<<endl;
return 0;
}
Nice~ 是我能看懂的压缩前写法!