C++ 代码
//f(i,j) = maxf(i-1,j-k*v[i]) + k *w[i]; 1
//从从j维看,f(i,j) = f(i-1,j) +f(i-1,j - v)+w,f(i-1,j-2v)+2w,...
// f(i,j-v)= f(i-1,j-v) + f(i-1,j - 2v) + w;
//f(i,j) = max(f(i,j-v) + w,f(i-1,j)); 2
#include<iostream>
using namespace std;
const int N = 1005;
int f[N],n,V,v[N],w[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 = 0; j <= V; ++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]);
// }
// }
// }
//简化
for(int i = 1 ;i <= n; ++i) {
for(int j = v[i]; j <= V; ++j) {//变化之数,位于f[i-1][j-v],要已知f[i-1][j-v] ,从j小状态到大状态,j = 0-v
f[j] = max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[V];
}