http://acm.hdu.edu.cn/showproblem.php?pid=1114原始代码:
//1308978 2009-04-25 19:39:15 Accepted 1114 546MS 312K 730 B C++ no way #include<iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int i,j,k; int c,e,f,n; int w[501],v[501],dp[10001]; scanf("%d%d",&e,&f); c = f - e; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(i=1;i<=c;i++) dp[i] = 1000000; for(i=0; i*w[1] <= c; i++) dp[i*w[1]] = i*v[1];
for(i=2;i<=n;i++) { for(k=0;k*w[i]<=c;k++)//所取物品数量 { for(j=k*w[i];j<=c;j++) { if(dp[j] > dp[j-k*w[i]] + k*v[i]) dp[j] = dp[j-k*w[i]] + k*v[i]; } } } if(dp[c] == 1000000) cout<<"This is impossible."<<endl; else cout<<"The minimum amount of money in the piggy-bank is "<<dp[c]<<"."<<endl; } return 0; }
优化代码:
//1309096 2009-04-25 20:12:49 Accepted 1114 93MS 384K 793 B C++ no way #include<iostream> struct node { int w; int v; }tt[10001]; using namespace std; int main() { int t; cin>>t; while(t--) { int i,j,k=1; int c,e,f,n; int dp[10001];//dp[i]表容量为i的时候所装东西的最小价值//w[10001],v[10001], scanf("%d%d",&e,&f); c = f - e; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&e,&f); tt[k].w = f; tt[k].v = e; while(1) { k ++; if(tt[k-1].w*2 > c) break; tt[k].w = tt[k-1].w * 2; tt[k].v = tt[k-1].v * 2; } } for(i=1;i<=c;i++) dp[i] = 1000000; dp[0] = 0;//背包容量为 0 啥也不能装 for(i=1;i < k;i++) { for(j=tt[i].w;j<=c;j++) { if(dp[j] > dp[j-tt[i].w] + tt[i].v) dp[j] = dp[j-tt[i].w] + tt[i].v; } } if(dp[c] == 1000000) cout<<"This is impossible."<<endl; else cout<<"The minimum amount of money in the piggy-bank is "<<dp[c]<<"."<<endl; } return 0; }
|