f[i]: 价值为I时,需要的最小体积
注意: 该解法会超时: 测试用例12/13。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
int f[N];
int n, m;
int main(){
cin >> n >> m;
memset(f, 0x3f, sizeof f);
f[0] = 0;
int mx = 0;
for(int i = 0; i < n; i++){
int vi, wi;
cin >> vi >> wi;
mx = max(mx, (m + vi - 1)/ vi * wi);
for(int j = wi; j <= mx; j++){
f[j] = min(f[j], f[j - wi] + vi);
}
}
int res = 0;
for(int j = mx; j >= 0; j--){
if(f[j] <= m){res = j; break;}
}
cout << res << endl;
return 0;
}