贪心算法最的硬币问题

        问题：有1元，5元，10元，50元，100元，500元的硬币各C1,C5,C10,C100,C500个，用这些硬币支付A远，最少需要多少硬币？

        1.0<=C<=10e10;

        2.0<=A<=10e9;

1. 贪心算法，如其名字，对于每次的硬币选择我均要求最好，即遵循最优策略。此题的最优策略便是“优先选取面值大的硬币使用”。
2. 下面我们思考代码所需部分：
   1. 1）变量：
      1. 存储硬币面值（coin[6]）
      2. 存储相应面值硬币个数（C[6])
      3. 记录支付的钱数（A）
      4. 记录所需硬币个数（sum）

                            2）实现主要代码块（硬币选择）

遵循最优策略，我们每次尽可能多的选取大面值硬币，即选择t = min（A /coin[i],C[i])个硬币，计算剩余待支付面值A，重复上述步骤。很明显可以通过循环或者递归来实现，这里我贴出循环的方法。

1.  
2.  
3.  
   #include <iostream>
4.  
   #include<algorithm>
5.  
   using namespace std;
6.  
   int main()
7.  
   {
8.  
   int coin[6] = { 1,5,10,50,100,500 };//存储硬币的大小
9.  
   int C[6];//存储硬币的个数
10.  
    for (int i = 0; i < 6; i ) {
11.  
    cin >> C[i];
12.  
    }
13.  
    int A;
14.  
    cin >> A;
15.  
    int sum = 0;//记录所需硬币个数
16.  
    for (int i = 5; i >= 0; i--) {
17.  
    int t = min(C[i], A / coin[i]);
18.  
    A -= t * coin[i];
19.  
    sum = t;
20.  
    }
21.  
    cout << sum;
22.  
    }
23.  
     
24.  
25.  
     
26.  

这篇好文章是转载于：学新通技术网