贪心算法的概念与使用

一、概念解析

        利用贪心算法对问题求解时，总是做出在当前情况下最好的选择。也就是说，贪心算法不是从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

        贪心算法没有固定的框架，该算法的关键是贪心策略的选择。贪心算法的基本思路如下：

1. 建立数学模型以描述问题；
2. 把求解的问题分成若干个子问题；
3. 把每个子问题进行求解，得到子问题局部最优解；
4. 把子问题的局部最优解合并成原来问题的解。

        贪心算法不能保证求的的最后解是最优解，所以贪心策略的前提是：局部最优策略能产生全局最优解。

        贪心算法的实现框架：

while(超给顶目标前进一步)
{
	利用可行的决策，求出可行解的第一个解元素;
}
由所有的届组合成问题的解;

         为了更方便大家理解，我引出几个例题。

二、例题分析

【题目内容】小明去超市购物，放到购物车中的食品如下。但小明当前能够拎回家的最大重量W=15斤，则小明如何选择最多的食物拎回家？

【思路分析】

        分析：想要得道最多的食物，我们每次应当选择最轻的那一个。

        我们把这些食物sort一下（排序方法可以参考我的相关文章）。按重量排序后食物清单如下表所示。

        按照贪心策略，我们每次选择重量最轻的食物放入袋中。

        我们先来执行一下贪心策略，验证一下是否正确。

        i=0，排序后的第1个，袋中的重量count=1，不超过重量极限15，ans=1。

        i=1，排序后的第2个，袋中的重量count=1+2=3，不超过重量极限15，ans=2。

        i=2，排序后的第3个，袋中的重量count=3+2.8=5.8，不超过重量极限15，ans=3。

        i=3，排序后的第4个，袋中的重量count=5.8+3.3=9.1，不超过重量极限15，ans=4。

        i=4，排序后的第5个，袋中的重量count=9.1+4.5=13.6，不超过重量极限15，ans=5。

        i=5，排序后的第6个，袋中的重量count=13.6+6.2=19.8，已经超过了重量极限15，算法结束。

        所以，最终小明可以带回家的食物个数为5。

代码如下

float max;
int n;
float a[11];
int ans=0;
int count=0;
sort(a+1,a+1+n);
for(int i=1; i<=n; i++)
{
	count+=a[i];
	if(count<=max)
	{
		ans++;
	}
	else
	{
		cout<
		break;
	}
}

---

好啦，以上就是本文的全部内容啦！