【题目描述】 作為创造產奶纪录的回报，Farmer John决定开始每个星期给Bessie一点零花钱。 FJ有一些硬币，一共有N (1 <= N <= 20)种不同的面额。每一个面额都能整除所有比它大的面额。 他想用给定的硬币的集合，每个星期至少给Bessie某个零花钱的数目C (1<=C<=100000000)。请帮他计算他最多能支付多少个星期的零花钱。 【输入格式】 第一行: 两个由空格隔开的整数: N和C 第2到第N+1行: 每一行有两个整数表示一个面额的硬币：硬币面额V (1<=V<=100,000,000)和Farmer John拥有的该面额的硬币数B (1<=B<=1,000,000) 【输出格式】 一个单独的整数表示Farmer John最多能给Bessie支付多少个星期至少為C的零用钱 【样例输入】 3 6 10 1 1 100 5 120 【样例输出】 111 【分析】 从样例就可以发现，我们完全可以先把v中大于等于C的先全部支付。这显然是正确的，因为没有必要在已经满足条件时还多给Bessie一些零钱，除非是Bessie自己在写这题。 然后对于每一个星期，尽量取大的面额使得总钱数不超过C，取完后如果没有达到C就找小的面额来补。通俗的说，大的面额是主力，小的面额是救火队员，哪里缺了就补上。用程序语言就是说，当前在使用面值为v[i]的钱，已经支付了j元，而且j+v[i]或v[i-1]>j+v[1]>=C，此处默认v数组已经按照从小到大的顺序排好了。
var a,b:array[0..21] of longint; i,n,c,sum,t:longint; change:boolean; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; temp:=b[i];b[i]:=b[j];b[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin sum:=0; readln(n,c); for i:=1 to n do readln(a[i],b[i]); qsort(1,n); change:=true; while change do begin change:=false; t:=c; for i:=n downto 1 do//先取大的面额 while (b[i]>0)and(t-a[i]>=0) do begin dec(b[i]); t:=t-a[i]; end; for i:=1 to n do//救火队员出场 if (b[i]>0)and(t>0) then begin dec(b[i]); t:=t-a[i]; end; if t<=0 then begin//这个星期支付完毕 change:=true; inc(sum); end; end; write(sum); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533504.html
相关资源：JAVA上百实例源码以及开源项目