贪心算法思想和应用_算法设计与分析:贪心算法思想的应用

1. 算法思想

当一个问题具有最优子结构性质时，可以用动态规划法求解，但有时使用贪心算法更简单，更直接而且解决问题的效率更高。

例如前面动态规划算法中的硬币问题就可以用贪心算法解决，从算法名字上来看，贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择，当然最终希望贪心算法得到的最终结果也是最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但是对于很多问题它能够产生整体最优解，或者最趋近于最优解。

一般用贪心算法解决问题提问都是：最多、最少、最大、最小。

2. 硬币问题

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int arr[] = { 1,3,5 };
	int length = sizeof(arr) / sizeof(arr[0]);
	int c = 11;
	sort(arr, arr + length, [](int a, int b)->bool {return a > b; });
	
	int idx = 0;//{5,3,1}
	int cnt = 0;//记录硬币个数
	while (c > 0)
	{
		if (c >= arr[idx])
		{
			c -= arr[idx];
			cnt++;
		}
		else
		{
			idx++;
		}
	}
	cout << cnt << endl;
}
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

3. 部分背包问题
   有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高，每一个物体都可以只取走一部分，价值和重量按比例计算，求最大总价值。
   （贪心算法—01背包，不一定得到最优解）

#include<iostream>
#include<algorithm>
using namespace std;

struct Product
{
	double getPrice()const
	{
		return v * 1.0 / w;
	}
	bool operator>(const Product& p)const
	{
		return getPrice() > p.getPrice();
	}
	int id;//物品的id
	int w;//物品重量
	int v;//物品价值
};
int main()
{
	int w[] = { 8,6,4,2,5 };
	int v[] = { 6,4,7,8,6 };
	const int n = sizeof(w) / sizeof(w[0]);
	int c = 12;
	int x[n] = { 0 };

	Product pros[n];
	for (int i = 0; i < n; i++)
	{
		pros[i].id = i;
		pros[i].w = w[i];
		pros[i].v = v[i];
	}
	//按物品的性价比降序排列
	sort(pros, pros + n, [](const Product& p1, const Product& p2)->bool {return p1 > p2; });
	
	double bestv = 0.0;//记录背包的最大价值
	for (int i = 0; i < n; i++)
	{
		if (pros[i].w <= c)//说明第i个物品可以装入背包
		{
			c -= pros[i].w;
			bestv += pros[i].v;
			x[pros[i].id] = 1;
		}
		else//第i个物品只能部分装入背包，按剩余容量的比例装入
		{
			bestv += pros[i].v * (c * 1.0 / pros[i].w);
			x[pros[i].id] = 1;
			break;
		}
	}
	cout << "bestv:" << bestv << endl;
	for (int v : x)
	{
		cout << v << " ";
	}
	return 0;
}
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
55
56
57
58
59

4. m个柜台提供服务，每个柜台给一个用户提供服务的时间是t（用数组表示每一个柜台提供服务的时间），问怎么排列，使得柜台服务给所有用户提供服务的时间最少。

#include<iostream>
#include<algorithm>
using namespace std;
//描述柜台
struct Counter
{
	bool operator<(const Counter& c)
	{
		return time < c.time;
	}
	int id;
	int time;
};

int main()
{
	int arr[] = { 3,2,4 };//给一个柜台提供服务的时间
	const int m = sizeof(arr) / sizeof(arr[0]);//柜台数量
	int c = 15;//办理业务人数
	
	//定义柜台信息数组
	Counter cons[m];
	for (int i = 0; i < m; i++)
	{
		cons[i].id = i;
		cons[i].time = arr[i];
	}
	//按照柜台提供服务时间升序排列
	sort(cons, cons + m);

	int mintime = 0;//记录给所有用户提供服务的最少时间
	int x[m] = { 0 };//记录每一个柜台安排的用户数量
	for (int i = 0; i < c; i++)
	{
		//先计算把i用户放在0号柜台的时间
		int time = cons[0].time * (x[0] + 1);
		int j = 1;
		//再遍历其他柜台看是否可以得到更少花费时间
		for (; j < m; j++)
		{
			int t = cons[j].time * (x[j] + 1);
			if (t < time)//放在其他柜台处理更快，直接放入j柜台
			{
				x[j]++;
				//新添加一个人，整体花费时间可能变得更长了，更新mintime
				if (t > mintime)
				{
					mintime = t;
				}
				break;
			}
		}
		//最终还是放在0号柜台花费时间最少
		if (j == m)
		{
			x[0]++;
			//更新mintime
			mintime = time;
		}
	}
	cout << "mintime:" << mintime << endl;
	for (int i = 0; i < m; i++)
	{
		cout << arr[i] << ":" << x[i] << endl;
	}
	return 0;
}
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
55
56
57
58
59
60
61
62
63
64
65
66
67