NYOJ 995 硬币找零

硬币找零

描述

在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。 我们应该注意到，人民币的硬币系统是 100，50，20，10，5，2，1，0.5，0.2，0.1，0.05， 0.02，0.01 元，采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。 但不幸的是： 我们可能没有这样一种好的硬币系统， 因此用贪心算法不能求出最少的硬币数，甚至有些金钱总数还不能用这些硬币找零。例如，如果硬币系统是 40，30，25 元，那么 37元就不能用这些硬币找零；95 元的最少找零硬币数是 3。又如，硬币系统是 10，7，5，1元，那么 12 元用贪心法得到的硬币数为 3，而最少硬币数是 2。 你的任务就是：对于任意的硬币系统和一个金钱数，请你 编程求出最少的找零硬币数； 如果不能用这些硬币找零，请给出一种找零方法，使剩下的钱最少。

输入

输入数据：
第 1 行，为 N 和 T，其中 1≤N≤50 为硬币 系统中不同硬币数；1≤T≤100000 为需要用硬币找零的总数。
第 2 行为 N 个数值不大于 65535 的正整数，它们是硬币系统中各硬币的面值。

当n，t同时为0时结束。

输出

输出数据：
如 T 能被硬币系统中的硬币找零，请输出最少的找零硬币数。
如 T 不能被硬币系统中的硬币找零，请输出剩下钱数最少的找零方案中的最少硬币数。

样例输入

4 12
10 7 5 1

样例输出

2

思路：就是个01背包问题类似，只是求的是最小值

代码：

# include 
      
       
# include 
       
         # define min(a,b)a
        
          复制去Google翻译翻译结果 
        
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

<script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力??

上一篇： LeetCode题解： LRU Cache 缓存设计

下一篇： 最后一页

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");