当前位置: 首页 > news >正文

算法设计与分析 实验五 贪心算法

1.活动选择:n项活动,每个活动指定起止时间,如果要求活动时间互不重叠,最多可以安排多少个活动。

入:每组数据第一行正整数 1n10000,接下来 n 行每行两个正整数 1s<t10000,表示活动起止时间戳。

出:最多可以安排的时间互不重叠的活动个数

入:10   1 4   3 5   2 6   4 9   5 9   8 11   5 7   6 10   8 12   2 13

出:3

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct node{
	int begin,end;
}dong[10000],temp;
bool hanshu(node a,node b){
	return a.end<b.end;
}
int main(){
	int n;int m=1;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>dong[i].begin>>dong[i].end;
	}
	sort(dong,dong+n,hanshu);
	int temp=dong[0].end;
	for(int i=1;i<n;i++){
		if(temp<=dong[i].begin){
			m++;
			temp=dong[i].end;
		}
	}
	cout<<m<<endl;
	return 0;
}

2.最优装载:有一个载重为n的大卡车,有m个货物要运送,给出货物的重量。假设卡车无限大,载货量仅受载重量限制,问最多一次能载多少个货物

入:输入第一行包含一个正整数t(t104),代表共有t组实例。每组实例第一行包含两个正整数nm(1n,m104),分别代表卡车的载重和货物数量。接下来m行,每行包含一个正整数x(1x50),代表第i个物品的重量

出:对于每组实例,每行仅输出一个正整数,表示最多一次能装载的货物数量。

入:1   10 4   3  4  5  6    出:2

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int t;cin>>t;
	while (t--) {
		int n, m;
		cin>>n>>m;
		int* a=new int[m];
		for (int i = 0; i<m;i++) {
			cin>>a[i];
		}
		sort(a,a+m);   
		int sum=0; int k=0;
		for (int i=0;i<m;i++) {
			sum+=a[i];
			if (sum<=n){
				k++;
			}
			else{
				break;
			}
		}
		cout<<k<<endl;
	}
	return 0;
}

3.找零钱:现有100,50,20,10,5,2,1元的纸币,现在一个物品价值n元,问至少需要多少张钱,才可以支付该物品。

入:输入多组数据,每组第一行输入整数n(1≤n≤9999)。

出:输出至少需要的钱的张数,并输出方案(输出格式:币值*张数+币值*张数+….=n,币值从大到小输出,其中张数为1则无需乘以张数)

入:6   1    1000     出:2 5+1=6   1 1+1   10 100*10=1000

#include<iostream>
using namespace std;
int main() {
	int value[7] = { 100,50,20,10,5,2,1 };
	int n, temp;int k = 0;
	while (cin>>n) {
		int sum = 0;//记录需要纸币的总张数
		temp = n;
		int thing[7]= {0}; //记录这种纸币张数
		for (int i = 0; i < 7; i++) {
			thing[i] = n / value[i];//更新这种纸币需要张数
			n %= value[i] ;//更新n
			sum += thing[i];//记录总张数
			//cout<<i<<endl;
		}
		cout << sum << " ";//输出总张数
		n=temp;
		for (int i = 0; i < 7; i++) {
			if (thing[i] > 0) {
				if (thing[i] == 1) {
					cout << value[i];
				} else {
					cout << value[i] << "*" << thing[i];
				}
				n =n - thing[i] * value[i];
				if (i < 6 && n > 0) {
					cout << "+";
				}
			}
		}
		cout<<"="<<temp<<endl;
	}
	return 0;
}

4.最小延迟调度:假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务,其中的每个任务 i 包含一个持续时间 ti 和截止时间 di 。设计与实现一个算法,从 0 时刻开始任务,对这组任务给出一个最优调度方案,使其所有任务中的最大延迟最小化。任务 i 的延迟指实际完成时间fi减去截止时间di

入:第一行输入一个t,代表有t组样例。(t≤10)

每个样例第一行输入一个n(n≤100),代表工作数,接下来n行,每行输入两个数ti(1≤ti≤100)和di(1≤di≤1000),代表任务持续时间和截止时间。

出:输出所有任务中的最大延迟的最小值

入:1  6  3 6  2 8  1 9  4 9  3 14  2 15  出:1

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 110;
class node {
	public:
		int t, d;
		bool operator<(const node& b)const {
			return d < b.d;
		}
};
int main() {
	node temp[maxn];
	int m, n;
	cin >> m;
	for (m; m--; ) {
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> temp[i].t >> temp[i].d;
		}
		sort(temp, temp + n);
		int x = 0, y = 0;
		for (int i = 0; i < n; i++) {
			int woo=temp[i].t + x - temp[i].d;
			y = max(woo, y);
			x += temp[i].t;
		}
		cout << y << endl;
	}
	return 0;
}

5.寻宝:XHD去寻宝,找到多种宝贝,每种宝贝单位体积的价格不一样,现在请你帮忙计算XHD最多能带多少价值的宝贝?(假设宝贝可以分割,分割后的价值和对应的体积成正比)

入:输入包含多个测试实例,每个实例的第一行是两个整数v和n(v,n<1000),分别表示口袋的容量和宝贝的种类,接着的n行每行包含2个整数pi和mi(0<pi,mi<1000),分别表示某种宝贝的单价和对应的体积,v为0的时候结束输入。

出:对于每个测试实例,请输出XHD最多能取回多少价值的宝贝,每个实例的输出占一行。

入:2 2   3 1   2 3  0    出:5

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct str {
	int pi,mi,s;
	bool operator < (const str& a) const {
		if(pi != a.pi) {
			return pi > a.pi;
		} else {
			return mi > a.mi;
		}
	}
};
int main() {
	int v, n;
	while(cin >> v && v != 0) {
		cin >> n;
		str mum[n];
		for(int i = 0; i < n; i++) {
			cin >> mum[i].pi >> mum[i].mi;
			mum[i].s = mum[i].pi * mum[i].mi;
		}
		sort(mum, mum + n);
		int sum = 0;
		for(int i = 0; i < n; i++) {
			if(v >= mum[i].mi) {
				v -= mum[i].mi;
				sum += mum[i].s;
			} else {
				sum += v * mum[i].pi;
				v = 0;
			}
			if(v == 0) {
				break;
			}
		}
		cout << sum << endl;
	}
	return 0;
}

6.最少拦截系统:某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.

由于成本所在,我们要用尽可能少的拦截系统,请帮忙算一下最少需要多少套拦截系统方可抵御一次进攻。

入:输入若干组数据.每组数据包括:导弹总个数,导弹依次飞来的高度。

第一个数输入n(1≤n≤100),代表有n个导弹,接下来在同一行中,输入n个数,代表导弹依次飞来的高度。

出:对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

入: 8   389   207  155  300  299  170  158  65   出:2

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int x = 100000;
int a[x], b[x], n;
int main() {
	while(cin >> n) {
		for(int i=1; i<=n; i++) {
			cin >> a[i];
		}
		int len = 1;
		b[1] = a[1];
		for (int i=2; i<=n; i++) {
			if(b[len] < a[i]) {
				b[++len] = a[i];
			}
			else {
				int p = lower_bound(b + 1, b + 1 + len, a[i]) - b;
				b[p] = a[i];
			}
		}
		cout << len << endl;
	}
	return 0;
}

7.多设备区间调度:多个调度任务,给出调度任务的起始时间和结束时间,问至少需要多少个设备能完成调度任务,在保证最小设备的情况,要求所有设备运行总时长最短。

每个设备的运行时长:从给这个设备的第一个任务开始计算到这个设备的最后一个任务结束,中间哪怕没有任务也要计算运行时长。

入:输入的第一行包含一个正整数t(t≤100),代表共有t组输入实例。每组输入实例中,第一行包含一个正整数n(n≤100),接下来输入n行,每一行包含两个正整数lr(0≤l<r≤109),分别一个调度任务的开始时间和结束时间l,r。读入至文件结束为止。

出:每组实例输出两个正整数,分别代表使用设备的数量,设备运行的总时长,每组实例输出占一行

入:1    5    1 3  3 6  2 4  5 7  6 9   出:2 13

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	long long n;long long shuzu[20000];long long temp = 0;
    while(cin>>n)
    {
        for(long long i = 0; i < n; i ++){
        	cin>>shuzu[i];
		}
        sort(shuzu, shuzu + n);
        long long x = 0;
        for(long long i = 0; i < n; i ++)
        {
            x=x+shuzu[i];
            temp=temp+x;
            x=x+shuzu[i];
        }
        cout<<temp;
    }
    return 0;
}

相关文章:

  • 正式环境关闭swagger
  • 动态内存的开辟
  • 【分布式版本控制系统Git】| IDEA 集成 Git 、IDEA 集成 GitHub
  • C语言指针链表
  • 全网最完整,接口测试总结彻底打通接口自动化大门,看这篇就够了......
  • 【JVM虚拟机面试宝典】JVM的内存结构是怎么样的?在JVM中会发生内存溢出的区域有那些?— day06
  • C++ string类
  • 细数那些惊艳一时的 CSS 属性
  • 【C语言】你真的了解结构体吗
  • 可做题2(矩阵快速幂,乘法逆元,exgcd)
  • Mysql用户权限分配详解
  • 一文7个步骤从0到1教你搭建Selenium 自动化测试环境
  • 【网络安全工程师】从零基础到进阶,看这一篇就够了
  • 【C陷阱与缺陷】----语法陷阱
  • 解忧杂货铺(五续集):用了无法离开的网站资源
  • 【跃迁之路】【477天】刻意练习系列236(2018.05.28)
  • CentOS 7 修改主机名
  • Computed property XXX was assigned to but it has no setter
  • Docker 笔记(2):Dockerfile
  • Laravel Telescope:优雅的应用调试工具
  • open-falcon 开发笔记(一):从零开始搭建虚拟服务器和监测环境
  • Sequelize 中文文档 v4 - Getting started - 入门
  • 创建一个Struts2项目maven 方式
  • 基于Javascript, Springboot的管理系统报表查询页面代码设计
  • 漫谈开发设计中的一些“原则”及“设计哲学”
  • 前端学习笔记之原型——一张图说明`prototype`和`__proto__`的区别
  • 使用前端开发工具包WijmoJS - 创建自定义DropDownTree控件(包含源代码)
  • 一起参Ember.js讨论、问答社区。
  • 【运维趟坑回忆录 开篇】初入初创, 一脸懵
  • ​软考-高级-系统架构设计师教程(清华第2版)【第15章 面向服务架构设计理论与实践(P527~554)-思维导图】​
  • (Java数据结构)ArrayList
  • (阿里云在线播放)基于SpringBoot+Vue前后端分离的在线教育平台项目
  • (三十)Flask之wtforms库【剖析源码上篇】
  • (转)http协议
  • .NET 应用架构指导 V2 学习笔记(一) 软件架构的关键原则
  • .Net(C#)自定义WinForm控件之小结篇
  • [ 云计算 | Azure 实践 ] 在 Azure 门户中创建 VM 虚拟机并进行验证
  • [BT]BUUCTF刷题第8天(3.26)
  • [C/C++]数据结构 循环队列
  • [c++] 什么是平凡类型,标准布局类型,POD类型,聚合体
  • [C++]二叉搜索树
  • [CSS]CSS 字体属性
  • [CUDA 学习笔记] CUDA kernel 的 grid_size 和 block_size 选择
  • [Eclipse] 详细设置护眼背景色和字体颜色并导出
  • [Excel VBA]单元格区域引用方式的小结
  • [HackMyVM]靶场Boxing
  • [IE9] IE9 RC版下载链接
  • [leetcode]56. Merge Intervals归并区间
  • [Machine Learning] 领域适应和迁移学习
  • [math]判断线段是否相交及夹角
  • [nextjs]推荐几个很好看的模板网站
  • [NOI2005]聪聪与可可(期望)
  • [Python基础]Python文件处理小结
  • [Spring Data MongoDB]学习笔记--MongoTemplate插入修改操作
  • [uniapp] uni-ui+vue3.2小程序评论列表组件 回复评论 点赞和删除