注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1114 完全背包  

2014-05-16 22:04:49|  分类: 背包 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

小猪银行

时间限制:2000/1000 MSJava /其它)内存限制:65536 / 32768 KJava /其它)

的提交(S)10486接受提交(S5282

问题描述

以前ACM可以做任何事情,预算必须准备和获得必要的金融支持。这一行动的主要收入来自不可逆结合的钱(IBM)。背后的想法是简单的。每当一些ACM的成员有任何小的钱,他所有的硬币丢进一个扑满。你知道的,这个过程是不可逆的,硬币不能没有打破猪删除。一个足够长的时间后,应该有足够的现金支付的银行都需要支付。

但也带来了一个大问题。不可能确定多少钱在里面。因此我们可能会破坏猪成碎片,却发现没有足够的钱。显然,我们要避免这种不愉快的状况。唯一的可能性是衡量银行试图猜测有多少硬币里面。假设我们能够确定猪的重量完全和我们所知道的所有硬币一个给定的货币的权重。然后有一些最低数额的金钱在储蓄罐里,我们可以保证。你的任务是找出这种最坏的情况下,确定的存钱罐里的现金量最小。我们需要你的帮助。没有更多的过早断裂的猪!

输入

输入包含T测试用例。它们的数量(T)是基于输入文件的第一行。每个测试案例开始一行包含两个整数,E和F表示一个空的猪体重和猪装满了硬币。给出了克重量。没有猪的重量超过10公斤,即1<=E≤f≤10000。在每个测试案例的第二行,那里是一个整数N(1≤n≤500),给出了在给定的货币的硬币数量。接下来是N行,每一行指定的一种硬币。这些行每行包含两个整数,P W(1≤p<=50000,1<=W≤10000)。P是硬币的货币单位的价值,是它的重量在克。

输出

打印一行输出对于每个测试案例。该行必须包含一句“扑满里的钱的最低金额为X”,X是最少的钱可以用硬币与给定的总重量达到。如果体重不能达到准确打印一行“这是不可能的

#include<stdio.h>
int Min(int a,int b)
{
return a>b?b:a;
}
int t,e,f,n,p[10000],w[10000],dp[10000];
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&e,&f);
int weight=f-e;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&p[i],&w[i]);
}
for(i=0;i<=weight;i++)/*求最小的值,比较最大的*/
{
dp[i]=100000000;
}
dp[0]=0; /*不能全部都是最大的啊*/
for(i=0;i<n;i++)
{
for(j=w[i];j<=weight;j++)
{
dp[j]=Min(dp[j],dp[j-w[i]]+p[i]);/*从签到后的策越,完全背包*/
}
}
if(dp[weight]==100000000) printf("This is impossible.\n");
else
{
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[weight]);
}
}

}


  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017