大家一起數鋼镚，數鋼镚

大家一起數鋼镚，數鋼镚

題目描述

Nova君在經歷雙十一風暴後，不得不靠在一家便利店打工來維持生計。作為一名合格的收銀員，必須快速的計算價格並找錢個顧客。Nova君是個十足的硬幣控，喜歡金屬色閃閃的硬幣，所以找錢是都希望用盡可能少的硬幣。現在，假設收銀台有面值為1元、5元、10元、50元、100元、500元的硬幣各Ai、Bi、Ci、Di、Ei、Fi 個，需要找的錢的數額為A元，那最少需要多少個硬幣呢？假定至少存在一種找錢方案。

被jhljx附體而不會數數Nova君求助中......

輸入

多組測試數據（組數不超過10），對於每組數據，輸入兩行，第一行為6個正整數，分別代表1元、5元、10元、50元、100元、500元的硬幣個數，第二行為一個正整數A，代表需要支付的錢數。所有正整數都在INT范圍內。

輸出

對於每組數據，輸出一行，為最少的硬幣數量

輸入樣例

3 2 1 3 0 2
620

輸出樣例

6

Hint

放輕松，簽到題~
題目來源:http://biancheng.love/contest/23/problem/A/index

解題方法：貪心算法
根據題目需要得到最少的硬幣個數（不要問我問什麼會有那麼大面值的硬幣）。考慮一種很實際的問題，比如說你去超市購物，營業員需要找零50元，那麼你肯定不希望營業員找給你的錢都是1毛1毛錢。也不想都是1塊1塊。一般的營業員可能找零50面額的，也可能是10張5元的，或者25張2元的（好久沒見過兩元紙幣了）等等方法。可以看出來找零最少的肯定是直接給一張50元。這就是我們很實際的貪心問題。因此營業員在找零的時候先去拿面值最大的並且小於找零。當滿足條件之後，將找零數目減去適合的最大面值，再次進行上述操作，直到找零結束。這樣的方法是很實際的貪心問題的應用。
貪心算法的博客推薦：http://www.cnblogs.com/chinazhangjie/archive/2010/11/23/1885330.html
下面給出本題的代碼：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 int main()
 5 {
 6     int a[7];
 7     int b[7]={0,1,5,10,50,100,500};
 8     int num;
 9     while(cin>>a[1]){
10     int ans=0;
11     for(int i=2;i<=6;i++)
12         cin>>a[i];
13     cin>>num;
14     for(int i=6;i>=1;i--)
15     {
16         while(num-b[i]>=0&&a[i]>0)
17         {
18             a[i]--;
19             ans++;
20             num-=b[i];
21         }
22     }
23     cout<<ans<<endl;
24     }
25 }