#include<iostream> #include<cstring> #define N 1005 struct app { int c,w; }a[N]; using namespace std; int main() { int n,v; while(cin>>n>>v && (n && v)) { int b[v+1]; memset(b, 0, sizeof(b)); for(int i = 0; i < n; i++) cin>>a[i].c>>a[i].w; for(int i = 1; i <= n; i++) for (int j = v;j >= a[i-1].c; j--) { b[j] = b[j] > (b[j - a[i-1].c] + a[i-1].w) ? b[j] : (b[j - a[i-1].c] + a[i-1].w); } cout<<b[v]<<endl; } return 0; }
原文:http://blog.csdn.net/liuxucoder/article/details/23123969