企业官网建设流程全解析

学习目标

1. 贪心算法的原理
2. 贪心策略与证明
3. 典型贪心算法问题

操作系统的发展

第一代(20世纪40年代)
·电子管
· 无操作系统
第二代(20世纪50年代)
晶体管
· 单道批处理系统
第三代(20世纪60年代)
·中小规模集成电路
· 多道批处理系统
第四代(20世纪70年代至今)
· 大规模集成电路
· 现代操作系统
操作系统的发展大致分为4个阶段。第一代的电子管计算机诞生于20世纪40年代,当时操作系统尚未出现,程序员直接与硬件打交道;第二代的晶体管计算机始于20世纪50年代,为了提高计算资源的使用效率,减少空闲时间,提出了单道批处理系统;
20世纪60年代,随着小规模集成电路的发展,出现了多道批操作系统,以进一步提高资源的使用效率;20世纪70年代,大规模集成电路飞速发展,操作系统百家争鸣,涌现出UNIX、DOS、Windows、Mac OS、Linux等著名的操作系统。

什么是贪心

小偷:先偷最值钱的财物 吃货:先吃最大的苹果

贪心算法

●贪心算法的原理是:

1. 将求解过程分成若干个步骤
2. 在每个步骤都应用贪心原则,选取当前状态下最好的或最优的选择(局部最优解)
3. 并以此希望最后堆叠出的结果也是最好或最优的解(整体最优解)希望“从局部最优解得到整体最优解”
   ● 贪心算法的关键是贪心策略,即按什么标准进行贪心选择

找零问题(一)

假如某国发行的货币有25分、10分、5分、1分四种硬币,如果你是售货员,你要找给客户41分钱的硬币,如何安排能使得找给客人的钱正确,但是硬币个数最少?

贪心策略

总是先选择不大于且最接近剩余金额的硬币
有没有比这种组合更少的硬币个数?没有,这种情况下,贪心算法可以得到整体最优解。
41 - 25 = 16
16 - 10 = 6
6 -5 = 1
硬币组合发生了变化

找零问题(二)

假如某国发行的货币有25分、20分、5分、1分四种硬币,如果你是售货员,钱的硬币,如何安排能使得找给客人的钱正确,但是硬币个数最少?

推翻贪心算法:只需要找到一个反例!

有没有比这种组合更少的硬币个数?
有。最优解应该是20、20、1!

对于某些硬币面值组合,贪心算法并不能找到最优解

本题正确的算法应该是动态规划(会在后面的课程中介绍)

贪心与证明

可以大胆猜想贪心策略,但要保证正确性(局部最优解一定能得到全局最优解)

一般用两种办法证明贪心成立。

1. 反证法:假设所选方案非贪心算法所要求的方案,只需要证明将需要贪心的方案替换掉所选方案,结果会更好(至少不会更差)
2. 数学归纳法:每一步的选择都是到当前为止的最优解,一直到最后一步就成为了全局的最优解。
   但实际上对于许多问题,证明贪心成立并非易事。
   我们往往只能凭借直觉或举例子来给出一个模棱两可的答案,而难以给出严谨的数学证明。

典型的贪心算法问题

已知哪些问题可以用贪心算法得到最优解?

· 硬币找零问题(在某些硬币组合下,贪心算法可以得到最优解)
· 部分背包问题
· 会议室相关问题(有若干个活动需要使用同一个会议室,每个活动有对应的开始时间和
结束时间,要求选取尽可能多的活动,使得任两个安排的活动时间不重叠)
· 任务调度问题(有若干个需要完成的任务和多个可执行任务的处理器,要求将任务分配
给处理器,使得执行总时间最小)
· 删数问题
· 均分纸牌问题

·….

部分背包问题

有n个物品,第i个物品的重量为Wi,价值为Vi。要求把物品装入背包载重量为C的背包,使背包内的物品价值最大。(物品可分割)

常识(直觉):同样重量的情况下,应该选价值最高的!

从单价高的开始装,装到不能装为止!

证明(反证法):
假设没在背包中放入单价高的物品,而放入了单价低的物品,那么可用等重量的
高价值物品替换掉背包里的低价值物品,总价值更高了。所以装入单价高的物品
是更优选择!

有n个物品,第i个物品的重量为Wi,价值为Vi。要求把物品装入背包载重量为C的
背包,使背包内的物品价值最大。(物品可分割)

第1个物体
w1=10
v1=60
v1/w1=6

第2个物体
W2=20
v2=100
v2/w2=5

第3个物体
W3=30
v3=120
v3/w3=4

第4个物体
w4=15
v4=45
v4/w4= 3
背包承重50
单价从高到底

单价(单位重量的价值)=价值/重量

注意】每个物品只能选择一次

贪心策略:先拿单位价值高的,装得下就全拿,否则进行分割。

部分背包问题的算法步骤:

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品,每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足,则使用当前物品的一部分填满背包。

部分背包也叫“分数背包”

贪心算法实现过程中一般都要先排序

举出了一个反例就可以推翻了一个错误的贪心算法

● 不可分割的背包问题,贪心策略(先拿单位价值高的)不能得到最优解
● 暂时放弃性价比最高的物品可能会让你获得更多

正确做法是搜索或者动态规划(会在后面的课程学习类似的题目)

先拿单位价值高的×

贪心算法-小结

●贪心算法是寻找问题最优解的常用方法之一
● 对于特定问题非常有效,但不是对所有问题都能得到整体最优解
● 归纳、分析、选择正确的贪心策略是贪心算法的关键
●对于某些问题可能需要复杂的证明来确保贪心策略的正确性

贪心没有套路,需要根据不同的题目选择贪心策略,并想办法证明正确性

多刷题、多练习是吃透贪心算法的唯一途径

部分背包问题

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞有n堆金币(n≤100),第i堆金币的总重量和总价值分别是wi、vi(1≤wi,vi≤100)。阿里巴巴有一个承重量为c(c≤1000)的背包,但无法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割,分割完的金币重量价值比(也就是单位价格)不变。请问阿里巴巴最多可以拿走多少价值的金币?
【输入格式】
第一行两个整数n,c。接下来n行,每行两个整数wi、vi。
【输出格式】
一个实数表示答案,输出两位小数。
【输入样例】

4 50

10 60

20 100

30 120

15 45

【输出样例】
240.00

贪心策略:先拿单位价值高的。

思路:

1. 排序:将物品按照单位价值从高到低进行排序。
2. 选择物品装包:顺序遍历所有物品,能装下就全部装包, 否则取当前物品的一部分填满背包。

1、排序

使用STL排序函数sort进行排序

1. 定义一个结构体gold用于存储某一堆金币的信息
2. 定义比较函数cmp进行两堆金币的比较

定义结构体gold,同时声明结构体数组a[]

structgold{intw;// 物品的重量intv;// 物品的价值doublep;单位重量的价值,v/w}a[101];

单价由v/w计算,保存为浮点数更精确

比较函数:单价高的排前面

boolcmp(gold a,gold b){if(a.p>b.p)returntrue;elsereturnfalse;}sort(a,a+n,cmp);// 排序

2、选择金币装包

· 数组a
· 背包的剩余容量cleft,初始为背包总容量c
· 已装入金币的总价值total,初始为0

第i堆金币:

1. 全部装入
2. 分割一部分装入
   切割价值=切割重量*单价

保存为浮点数更精确

doubletotal=0;intcleft=c;for(inti=0;i<n;i++){if(a[i].w<=cleft){//物品全部装入cleft-=a[i].w;total+=a[i].v;}else{//分割一部分,装满背包剩余容量total+=cleft*a[i].p;cleft=0;break;// 已装满马上停止循环}}

完整流程

1. 读取n,c
2. 读取n组金币数据,初始化金币数组a[]
3. 用sort对a[]进行(单价优先)排序
4. 顺序遍历a[],进行装包,并统计已装入金币的价值
5. 输出已装入金币的价值(保留两位小数)

intmain(){intn;intc;//背包容量cin>>n>>c;for(inti=0;i<n;i++){cin>>a[i].w>>a[i].v;a[i].p=a[i].v/a[i].w;}//物品数量sort(a,a+n,cmp);//进行单价优先排序//顺序遍历,进行装包doubletotal=0;intcleft=c;for(inti=0;i<n;i++){if(a[i].w<=cleft){//物品全部装入cleft-=a[i].w;total+=a[i].v;}else{//分割一部分,装满背包剩余容量total+=cleft*a[i].p;cleft=0;break;// 已装满}}printf("%.2lf\n",total);return0;}

#include<iostream>#include<algorithm>usingnamespacestd;structgold{intw;//物品的重量intv;//物品的价值doublep;//单位重量的价值,v/w}a[101];// 比较函数:性价比高的排前面boolcmp(gold a,gold b){if(a.p>b.p)returntrue;elsereturnfalse;}intmain(){intn;//物品数量intc;//背包容量cin>>n>>c;for(inti=0;i<n;i++){cin>>a[i].w>>a[i].v;a[i].p=a[i].v/a[i].w;}// 先排序sort(a,a+n,cmp);// 从单价高的开始装doubletotal=0;//装入背包的价值intcleft=c;//背包剩余容量for(inti=0;i<n;i++){if(a[i].w<=cleft){//第1个物品重量不超出背包剩余容量cleft-=a[i].w;//装入,剩余容量减少total+=a[i].v;//物品全部装入}else{//分割一部分,装满背包剩余容量total+=cleft*a[i].p;cleft=0;break;// 已装满}}printf("%.2lf\n",total);return0;

会议室安排

某会议室每天都会有许多活动,有些活动的计划时间会发生冲突,需要选择出一些活动进行举办。小刘的工作就是安排会议室的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能的安排最多的活动,请问他该如何安排?
【输入格式】每组测试数据的第一行是一个整数n(1 <= n <= 100)。随后的n行,每行有两个正整数Bi,Ei(0 <= Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi <= Ei)。
【输出格式】输出最多能够安排的活动数量。
【输入样例】
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
11个待选的活动
11行,每行:活动开始时间+活动结束时间
【输出样例】
4
最多能安排4个活动


贪心策略:选择具有最早结束时间,且不与已安排会议重叠的会议。

1. 实现步骤: 排序:首先将所有活动按结束时间升序排列。
2. 选择并计数:
   ①从排序后的活动列表中选择第一个活动进行安排。
   ②检查是否重叠:检查后续活动是否与已安排的活动有重叠。如果不重叠,则
   安排该活动;如果重叠,则跳过。
   ③ 重复:重复步骤2和3,直到所有活动都被检查完毕。

1、排序

使用STL排序函数sort进行排序
①定义一个结构体action用于存储活动的信息
② 定义比较函数cmp进行活动的比较

定义结构体action,同时声明结构体数组a[]

structaction{intb;//活动开始时间inte;//活动结束时间}a[101];

boolcmp(action a,action b){if(a.e<b.e)returntrue;elsereturnfalse;}sort(a,a+n,cmp);//排序

比较函数:先结束的排前面

2、选择并计数

1. 选择a[0]为第一个活动,初始化sum和end
2. 顺序遍历a[1]~a[n-1]
   · 如果与当前活动不重叠,则安排该活动:更新sum和end。
   · 否则跳过。
   · 数组a
   计数变量sum
   · 当前活动结束时间end

intsum=1;intend=a[0].e;for(inti=1;i<n;i++){if(a[i].b>=end){end=a[i].e;sum++;}}

完整流程

1. 读取n
2. 读取n组活动数据,初始化活动数组a[]
3. 用sort对a[]进行排序
4. 顺序遍历a[],选择会议并计数
5. 输出计数值

intmain(){intn;cin>>n;for(inti=0;i<n;i++)cin>>a[i].b>>a[i].e;sort(a,a+n,cmp);// 选择活动并计数intsum=1;intend=a[0].e;for(inti=1;i<n;i++){if(a[i].b>=end){cur=a[i].e;sum++;}}cout<<sum<<endl;return0;}

完整代码

#include<iostream>#include<algorithm>usingnamespacestd;structaction{intb;//活动开始时间inte;//活动结束时间}a[101];boolcmp(action a,action b){if(a.e<b.e)//先结束的排前面returntrue;elsereturnfalse;}intmain(){intn;cin>>n;for(inti=0;i<n;i++)cin>>a[i].b>>a[i].e;sort(a,a+n,cmp);// 以结束时间排序intsum=1;//排序后a[0]一定是第一个使用会议室的intend=a[0].e;//当前使用会议室的活动的结束时间for(inti=1;i<n;i++){if(a[i].b>=end){//选择与当前活动不相交的活动end=a[i].e;sum++;}}cout<<sum<<endl;return0;}

本次课程的知识点

1. 贪心算法的原理
2. 贪心算法与贪心策略的选择
3. 贪心法的证明和证伪演示:硬币找零、部分背包问题
4. 编程练习:部分背包问题、会议室安排问题
   
   

纪念品分组

元旦快到了,校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡,他要把购来的纪念品根据价格进行分组,但每组最多只能包括两件纪念品,并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品,乐乐希望分组的数目最少。你的任务是写一个程序,找出所有分组方案中分组数最少的一种,输出最少的分组数目。
【输入】共n+2行(0 <= n <= 50)。第一行包括一个整数w,为每组纪念品价格之和的上限。
第二行为一个整数n,表示购来的纪念品的总件数。第3~n+2行每行包含一个正整数Pi表
示所对应纪念品的价格。
【输出】一个整数,即最少的分组数目。
【输入样例】
100

9

90

20

20

30

50

60

70

80

90

【输出样例】
6

【提示】
贪心策略:优先一大、一小分组
算法步骤:

1. 将纪念品按价格由小到大排序。
2. 优先一大、一小,如果价格之和不超限,则分为一组,如果超限,则大的单独分为一组。
3. 重复以上过程,直到所有数据都遍历到(采用一头一尾双指针即可)。

#include<iostream>#include<algorithm>usingnamespacestd;constintN=55;inta[N],w,n,ans;intmain(){cin>>w>>n;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);//从小到大排序inti=1,j=n;//i左指针,j右指针while(i<=j){if(a[i]+a[j]<=w){//i,j之和不超w,两个组合打包ans++,i++,j--;}elseans++,j--;// 否则,(大的那个)j单独打包}cout<<ans;return0;}