贪心算法

发布于：2020年7月9日

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

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元硬币
我们优先使用面值大的硬币，这样可以更快满足数额要求同时又能用最少的硬币数量，是个典型的贪心、花心、“渣男”型算法。这就是所谓的贪心算法。

代码示例

#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();
}