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()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
cin>>t;
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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]);
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=1;i<=c;i++)
dp[i] = 1000000;
for(i=0; i*w[1] <= c; i++)
dp[i*w[1]] = i*v[1];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=2;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(k=0;k*w[i]<=c;k++)//所取物品数量
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=k*w[i];j<=c;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int w;
int v;
}tt[10001];
using namespace std;
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int t;
cin>>t;
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d",&e,&f);
tt[k].w = f;
tt[k].v = e;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(j=tt[i].w;j<=c;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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;
}
|