硬币找零.ppt

硬币找零 题目描述 在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。我们应该注意到，人民币的硬币系统是100，50，29，10，5，2，1，0.5，0．2，0．1，0．05，0．02，0．01元，采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。  题目描述 但不幸的是：我们可能没有这样一种好的硬币系统，因此用贪心算法不能求出最少的硬币数，甚至有些金钱总数还不能用这些硬币找零。例如，如果硬币系统是40，30，35元，那么37元就不能用这些硬币找零；95元的最少找零硬币数是3。又如，硬币系统是10，7，5，1元，那么12元用贪心法得到的硬币数为3，而最少硬币数是2。 题目描述 你的任务就是：对于任意的硬币系统和一个金钱数，请你编程求出最少的找零硬币数；如果不能用这些硬币找零，请给出一种找零方法，使剩下的钱最少。 题目描述 【输入格式】 ?? 第1行，为N和T，其中为1≤N≤5000硬币系统中不同硬币数；l≤T≤30000为需要用硬币找零的总数。第2行为N个数值不大于65535的正整数，它们是硬币系统中各硬币的面值。 【输出格式】 ???? 如T能被硬币系统中的硬币找零，请输出最少的找零硬币数。如T不能被硬币系统中的硬币找零，请输出剩下钱数最少的找零方案中的最少硬币数。 思路介绍 对于此题，可以举个例子： 若有1，5，7，10这四种货币，则易知 1=1 2=1+1 3=1+1+1 …… 6=5+1 思路介绍 那么推下去可知 表示12这个面值需要的货币数，等于表示11或7或5或2需要的货币数+1。 那么题中若要求表示12所需用的最小货币数，只需寻找表示11或7或5或2需要的货币数中的最小值。 思路介绍 思路介绍 那么对于任意的i来说， d[i]=min(d[i – a] )+1 (a∈{货币面值}且d[i – a] ≠0) {d[i]=0代表i无法用给定的货币表示} 程序 因此，就得到如下程序: var d:array[1..30000]of integer; {存储表示任意钱数的所需货币最小值} money:array[1..5000] of integer; {用于存储各种面值的货币} i,j,tt,pp,total,moneynum:integer; {moneynum代表货币种数，total表示要表示的面值} f:text; c:integer; 程序 assign(f,ybzl.in); reset(f); readln(f,moneynum,total); for i:=1 to moneynum do read(f,money[i]); close(f);{读入的过程} 程序 assign(f,ybzl.out); rewrite(f); for i:=1 to moneynum do for j:=1 to moneynum-1 do begin if money[j]money[j+1] then begin c:=money[j]; money[j]:=money[j+1]; money[j+1]:=c; end; end;{j}{这里对钱币进行从小到大的排序} （一会就有用了） 程序 if totalmoney[1] then writeln(f,0) else begin…… {若要表示的面值比最小的货币还小，就无法表示了} 程序 for i:=money[1] to total do if search(i) then d[i]:=1 else begin…… {search(i)是一个布尔型的函数，表示面值i是否在给定的面值中，是则返回true} {这段程序的含义是，若面值i是给定的面值之一，那么d[i]必定等于1} 程序 pp:=30000; tt:=1; while money[tt]i do begin if (d[i-money[tt]]pp)and(d[i-money[tt]]0)