贪心算法

概念解释

贪婪算法(贪心算法)是指在对问题求解的时候，每一步选择都采用最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。

贪心算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

贪心算法并没有固定的解发框架，算法的关键是贪心策略的选择，根据不用问题选择不同的策略。

基本思路

  • 建立数学模型描述问题
  • 把求解的问题分为若干个子问题
  • 对每一个子问题求解，得到子问题的局部最优解
  • 把子问题对应的局部最优解合成原来整个问题的一个近似最优解。

例题：

《钱币找零问题》

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0,c1,c2,c3,c4,c5,c6张。现在要用这些钱来支付K元，最少要用多少张纸币？

解题思路：

用贪心算法的思想，每一步都用能用的最大纸币即可。

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
using namespace std;

#define N 7
//有的零钱面值
int value[N] = { 1,2,5,10,20,50,100 };
//对应零钱的张数
int Vcount[N] = { 10,2,3,1,2,3,5 };

int solve(int money)
{
	int num = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		int j = money / value[i];//从最大面值开始，尽可能地用最大面值先支付，看看用几张
		int c = j > Vcount[i]?Vcount[i]:j;//看看有的张数够不够，够就用j，不够就用有的最大数量Vconut[i]
		if (j)
		{
			cout << "使用了" << c << "张" << value[i] << "的" << endl;
		}
		money -= c * value[i];
		num += c;
		if (money == 0)
		{
			break;
		}
	}
	
	if (money > 0)
	{
		return -1;//说明钱不够
	}
	return num;
}

int main(void)
{
	int money = 0;//钱
	int num = 0;//张数
	cout << "请输入要支付的价格" << endl;
	cin >> money;
	num = solve(money);
	if (num != -1)
	{
		cout << "最少要用" << num << "张" << endl;
	}
	else
	{
		cout << "前不够" << endl;
	}

	
	return 0;
}

但是，当我们只有1张50的和3张20的时候，money定位60块钱就会出现问题。 会提示找不开，这种情况下我们使用贪心算法得到的答案就不是最优解，因为我们一直在尝试用最大的纸币来尽可能的使用最少的张数来解决问题。这就不是最优的。

贪心算法没有固定的框架，关键是看你怎么选择。这种情况就需要调整策略，甚至，就不适用贪心算法。

贪心算法是尽力找到近似的最优解，注重的是速度，不是精准度，并不是说一定能找到合适的解,或是一定能找到解 。

对应问题根据情况不同选择合适的算法解决。