贪心算法–☟☟
贪心算法(贪婪算法):是一种遵循某种规则,不断贪心选取当前最优策略的算法设计方法。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
下面通过几个例子说明和学习贪心算法

1.硬币问题

有1元、5元、10元、50元、100元、500元的硬币各C₁、C₅、C₁₀、C₅₀、C₁₀₀、C₅₀₀枚。现在要用这些硬币来支付A元,最少需要几枚硬币?假定本题至少存在一种支付方案。
※限制条件

  • 0 <= C₁、C₅、C₁₀、C₅₀、C₁₀₀、C₅₀₀ <= 10⁹
  • 0 <= A <= 10⁹

样例

输入


C₁=3、C₅=2、C₁₀=1、C₅₀=3、C₁₀₀=0、C₅₀₀=2,A=620


输出


6(500元的1枚,100元的硬币1枚,50元的硬币2枚,10元的硬币1枚,5元的硬币2枚)


这个很容易根据我们的经验先从面值最大的硬币入手

  • 首先尽可能多地用500元的硬币
  • 其次再尽可能多地用100元的硬币
  • …………
  • 依次类推最后才用面值最少的1元硬币
    我们优先使用面值大的硬币,这样可以更快满足数额要求同时又能用最少的硬币数量,是个典型的贪心、花心、“渣男”型算法。这就是所谓的贪心算法。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;

const int v[6] = { 1,5,10,50,100,500 };//硬币面值
int c[6] = { 3,2,1,3,0,2 };
int A;//支付值

void solve() {
int ans = 0;//硬币枚数

for (int i = 5; i >= 0; i--) {
int t = min(A / v[i], c[i]);//避免0枚硬币的影响
A -= t * v[i];
ans += t;
}
cout << ans << endl;
}

int main() {
cin >> A;
solve();
}

本文首发于个人博客http://suzhigao66.top/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/)

评论