C++ 代码
#include <iostream>
using namespace std;
const int N = 1010;
int f[N]; // 二维数组优化为一维,因为状态传递只涉及原来二维数组的相邻两行
int w[N],v[N];
int n, V;
int main() {
cin >> n >> V;
for(int i = 0; i < n; i ++) cin >> v[i] >> w[i];
for(int i = 0; i < n; i ++) {
for(int j = V;j >= v[i] ; j --) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}