贪心算法学习感悟

  贪心算法就是遵循某种规则，不断选取当前最优策略的算法设计方法。

   2.2.1硬币问题

   要求：支付m元，现有给定面额为1，5，10，50，100，500这六种面额的硬币，各从C1，C2，C3，C4，C5，C6枚，求使用最少的硬币。

输入

620 3 2 1 3 0 2

输出

6

note：500元硬币一枚，50元硬币两枚，10元硬币一枚，5元硬币两枚，合计六枚

这是个贴近生活的简单问题。凭直觉可以做出以下解答：

首先尽可能多的使用500元硬币剩余部分尽可能多的使用100元硬币剩余部分尽可能多的使用50元硬币剩余部分尽可能多的使用10元硬币剩余部分尽可能多的使用5元硬币最后剩余部分用1元硬币支付

      简而言之

      优先使用面值最大的硬币

       如果用贪心算法无疑是一个高效解法

       AC

        

#include <iostream> #include <algorithm> using namespace std; int a[7] = {0,1,5,10,50,100,500}; int b[7]; int main() { int m; while(cin >> m) { int res = 0; for(int i = 1;i<= 6;i++) cin >> b[i]; for(int i = 6;i >= 1;i--) { int t = min(m/a[i],b[i]);//algorithm函数，比较取最优 m = m - t * a[i];//更新值 res += t; } cout << res <<endl; } return 0; }