王道机试2.6：贪心算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了王道机试2.6：贪心算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1091字，纯文字阅读大概需要2分钟。

内容图文

背包问题代码实现：

#include<stdio.h>
#include<algorithm>
using namespace std;
struct goods
{
	double j;
	double f;
	double s;
	bool operator < (const goods &A) const{
		return s>A.s;
	}
}buf[1000];
int main(){
	double m;
	int n;
	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);
		int idx = 0;
		double ans = 0;
		while (m>0&&idx<n)
		{
			if (m>buf[idx].f)
			{
				ans += buf[idx].j;
				m -= buf[idx].f;
			}
			else
			{
				ans += buf[idx].j*m / buf[idx].f;
				m = 0;
			}
			idx++;
		}
		printf("%.3lf\n", ans);
	}
	return 0;
}

活动调度：

#include<stdio.h>
#include<algorithm>
using namespace std;
struct program
{
	int startTime;
	int endTime;
	bool operator < (const program & A) const{
		return endTime < A.endTime;
	}
}buf[100];
int main(){
	int n;
	while (scanf("%d",&n)!=EOF)
	{
		if (n == 0){
			break;
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%d%d", &buf[i].startTime, &buf[i].endTime);
		}
		sort(buf, buf + n);
		int currentTime = 0, ans = 0;
		for (int i = 0; i < n; i++)
		{
			if (currentTime<=buf[i].startTime)
			{
				currentTime += buf[i].endTime;
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

内容总结

以上是互联网集市为您收集整理的王道机试2.6：贪心算法全部内容，希望文章能够帮你解决王道机试2.6：贪心算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---