’‘’
include[HTML_REMOVED]
using namespace std;
/
常规做法
状态表示 f[i][j]//表示选择前i个数,还要保证体积小于j 状态属性 max 求最大价值‘
状态计算
分为包含该物体和不包含该物体
f[i][j]=max(f[i-1][j],f[i-1][j-kv[i]]+kw[i])//注意这里还要考虑v[i]与j的关系 看 k<=j/v[i];
我们会发现一个关系 f[j]=max(f[j],f[j-v]+w[i])//这个关系是一维数组里面
/
const int N=100010;
int v[N],w[N],f[N];
int n,m;
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]);
}
}
cout<<f[m];
}
’‘’