阿坝州网站建设公司

复习-基础贪心-创新互联

贪心简介

贪心算法正如其名，贪心，意为每次都选择一个问题的子问题的最优情况，从而达到整体上的最优情况。

创新互联服务项目包括崇明网站建设、崇明网站制作、崇明网页制作以及崇明网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，崇明网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到崇明省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

但是贪心算法实际上是比较难用的，因为对于某些问题而言，每次选择最佳情况，最后不一定会达到整体上的最优情况，比如01背包问题，因为实际上01背包问题的特点就是每个个体是不可拆分的，对于贪心策略而言，必须具备无后效性，即某个状态以前的过程不会影响之后的状态。

例题1

P2240 【深基12.例1】部分背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于部分背包问题，因为对于某一个物体，我们可以任意分割，并且其性价比不变，所以我们可以采用贪心算法，对其性价比进行排序后，从高到低依次拿取，直到拿完或者背包容量不足。属于是入门级例题

#include#include#include 
using namespace std;
const int N = 1000;
struct Gold
{
	double w;
	double v;
	double ave;
};

Gold TP[N];

bool cmp(Gold a,Gold b){
	return a.ave >b.ave;
}

int main()
{
	int N, T; cin >>N >>T;
	float res = 0;
	for (int i = 0; i< N; i++)
	{
		cin >>TP[i].w >>TP[i].v;
		TP[i].ave = TP[i].v / TP[i].w;
	}
	sort(TP, TP + N,cmp);
	for (int i = 0; T>0&&i
例题2

P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题相比上题难度稍微大一点，但是也属于基础题（怎么求平均值稍微花了我一点时间）。因为如果第i人在排队，那么就同时有n-i人在等待，所以，sum+=(n-i)* V[i].first；贪心策略就不多说了。

#include#include#include 
#includeusing namespace std;
const int N = 1000;
vector>V(N, { 0,0 });
bool cmp(paira, pairb)
{
	return a.first< b.first;
}
int main()
{
	int n; cin >>n;
	double sum = 0;
	for (int i = 1; i<= n; i++)
	{
		cin >>V[i].first;
		V[i].second = i;
	}
	sort(V.begin()+1, V.begin()+n+1,cmp);
	for (int i = 1; i<= n; i++)
	{
		sum += (n-i)* V[i].first;
		cout<< V[i].second<< " ";
	}
	cout<< endl<< fixed<< setprecision(2)<< sum / n;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章名称：复习-基础贪心-创新互联
分享地址：http://azwzsj.com/article/ceihpp.html

其他资讯