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;
}
|