贪心算法

98 阅读 0 评论 65 点赞

我是靠谱客的博主迅速店员，最近开发中收集的这篇文章主要介绍贪心算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。

二、步骤
建立数学模型来描述问题
把求解的问题分成若干个子问题
对每个子问题求解，得到子问题的局部最优解
把子问题的解局部最优解合成原来问题的一个解

三、该算法存在的问题
不能保证求得的最后解是最佳的
不能用来求最大值或最小值的问题
只能求满足某些约束条件的可行解的范围

四、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似

例题：

1、题目的大致意思是：m元钱，n种物品，每种物品j磅，总价值f元，可以使用0到f的任意价格购买相应磅的物品，例如使用0.3f元，可以购买0.3j磅物品。要求输出用m元钱最多能买到多少磅物品。
输入：
输入m元，n种物品，后输入n种物品，以及每种物品对应的重量、总价值，输入-1，-1结束输入。
这题可以用贪心算法求解，对于剩余物品，每次都购买剩余物品中性价比（即重量/价格）最高的物品，直到该物品被买完，则我们继续在剩余的物品中寻找性价比最高的物品，重复该过程；若金钱耗尽，则交易结束

#include<bits/stdc++.h>
using namespace std;
struct goods
{
	double j;//每种物品的总重
	double f;//每种物品的总价值
	double s;//每件物品的性价比 
	bool operator<(const goods &A)const{
		return s>A.s;
	}
	
}buf[1000];
double m;//有m元 
int n;// 有n中物品 
int main()
{
	while(scanf("%lf %d",&m,&n)!=EOF)
	{
		if(m==-1&&n---1)
		{
			break;
		}
	
	for(int i=0;i<n;i++)
	{
		scanf("%lf %lf",&buf[i].j,&buf[i].f);
		buf[i].s=buf[i].j/buf[i].f;
	}
	
	sort(buf,buf+n);
	//以上是对物品的性价比进行排序
	
	//接下来明确一个问题，当从性价比由高到低排序后，因为要最多磅，所以性价比高的要全部买，到最后才剩多少买多少
	//SO
	
	int index=0;//定义当前买到第几个货物了 
	double bang=0;//定义已经买了的总磅数 
	while(m>0)
	{
		if(m>buf[index].f)//当钱还没有花完 
		{
			m-=buf[index].f;
			bang+=buf[index].j; 
		}
		else
		{
			bang+=buf[index].j*m/buf[index].f;//无法全部买的时候，能买多少买多少 
			m=0;//记得置零 
		}
		index++; 
	 } 
	  cout<<bang<<endl;
}
	return 0;
}

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa