【算法设计与分析zxd】第7章 贪心法

贪心算法的设计技术

• 每一步的判断都是一个当前最优的抉择，这个抉择计算设计的好坏，决定了算法的成败。

• 多步判断过程，最终的判断序列对应于问题的最优解

• 适用于 能够 由 局部最优达到全局最优的优化问题 【比如 求最短哈密顿回路的问题，就不是】

• 需要对具体的贪心算法的正确性进行必要的证明

用贪心法 求问题的解

【例7-1】

学生有n项活动申请使用某一个会议室，每项活动都有一个开始时间和一个结束时间。任何两个活动都不能同时使用这个会议室。问如何安排这些活动，使得被安排活动的数量达到最多？

问题分析

设活动编号的集合为A={1,2,…,n}，第i项活动的起始时间为si，

结束时间为e i 。满足s i ≥e j 或s j ≥e i，i≠j，称为活动相容。

求A的两两相容的最大活动子集S。

 方法1：按活动开始时间优先【更早的开始活动，也许能安排更多的活动】，例

A={1,2,3}，s 1 =0, e 1 =17, s 2 =3,e 2 =5,s 3 =8,e 3 =15

 方法2：按占用时间由短到长来选择，也许可能安排更多的活动，

例A={1,2,3}，s 1 =0, e 1 =8, s 2 =7,e 2 =10,s 3 =9,s e =15

 方法3：按结束时间从小到大选择，也许可以安排更多的活动。

命题：

活动是按结束时间从小到大进行排序的，即有

e 1 ≤e 2 ≤e 3 …≤e n ，贪心算法选择到第k步，有k项活动被选择，

生成一个选择序列i 1 ,i 2 , …,i k （按策略必有i 1 =1），

那么，最优解S必然包含i 1 ,i 2 , …,i k 。

【全局最优包含局部最优】

证明：设A中的活动都是按照结束的时间递增的顺序排列的，

S是A的最优解且S={i 1 ,i 2 , …,i m }。

(1) 当k=1时，需证明活动1被包含在最优解S中，即i 1 =1。

假设 i 1 ≠1，那么用活动1去替换i 1 ，得到S’，有S’=(S-{i 1 } ) ∪{1}，

因为活动1结束时间比i 1活动结束得更早，因此，其和i 2 , …,i m活动均相容，又由于S与S’数量相同，

所以，S’也是A的最优解。 命题成立。

(2)假设对于任意整数k，命题正确。

若前k步顺序选择的活动 为i 1 ,i 2 , …,i k ，那么存在一个最优解S={i 1 ,i 2 , …,i k }∪B。

如果令S’是S中剩下的与{i 1 ,i 2 , …,ik}相容的活动，S’S  

 那么B是S’的一个最优解。若不然，假如S’有解B’，B’>B，那么用B’替换B以后得到解{i1 ,i2 , …,ik}∪B’，将比S的活动更多，这与S是最优解矛题得证。

对比(1)的证明，算法第一步选择结时间最早的活动总是导致一个最优解，故对子

问题S’存在一个最优解B*={ i k+1 , …}。由于B*与B都是S’的最优解，因而B*=B。于是

S’={ i 1 ,i 2 , …,i k }∪B*={ i 1 ,i 2 , …,i k , i k+1 }∪(B-{ i k+1 })

S’与S的活动数目一样多，也是一个最优解，而且恰好包含了算法前k+1步选择的

活动。则命题得证。

1.排序2.相容性判定

计算模型

(1)存储结构：

struct Active{startTime s;//开始时间endTime e;//结束时间selectflag f;//选标识 
}A[n];

（2）计算：
活动i 与 活动j 相容 -> A[ i ].s >= A[ j ].e 或 A[ j ].s >= A[ i ].e

用归并排序 或 其他任何高效的排序算法完成 以a[i].e的从小到大 的排序，形成排序A[1].e≤A[2].e ≤…≤A[n].e

【例7-2】数列极差。

给定含有n个正整数的数列a，做如下两步操作：

(1)每一次删除其中的两个数a i 和a j ;

(2)在数列中加入一个数a i ×a j +1

循环执行步骤(1)(2)直到集合中只剩下一个元素为止。 【每种选择顺序会有不同的剩余的数】

设计 算法求得数列中剩余的数为最大值max和最小值min，

则该数列的极差为M=max-min。

问题分析

实例：设a={5,6,7}，那么，它将有三种组织方式：

(5*6+1)*7+1=218；

(5*7+1)*6+1=217；

(6*7+1)*5+1=216。

两个最小的数相乘，结果最大。

命题：

当一个数列中含有n(n>2)数时，该数列按数列极差法

求最大数值的方法为：每次选择数列中最小的两个数进行相乘加 1。

求最小数值为：每次从数列中选择两个最大的数相乘加1。

证明：

(1) 当k=3时，

数列a={a1 , a2 , a3}，不妨令a1< a2< a3 ，这样

可以设a 2 = a 1 +k 1 (k 1 >0)；a 3 = a 1 +k 1 +k 2 (k 1 ,k 2 >0)。那么这三个数的

三种组合方式为：

(a 1 * a 2 +1)* a 3 +1

= a 1 * a 1 * a 1 +(2*k 1 +k 2 ) *a 1 * a 1 +(k 1 *(k 1 +k 2 )+1)*a 1 +k 1 +k 2 +1

(a 1 * a 3 +1)* a 2 +1

= a 1 * a 1 * a 1 +(2*k 1 +k 2 ) *a 1 * a 1 +(k 1 *(k 1 +k 2 )+1)*a 1 +k 1 +1

(a 2 * a 3 +1)* a 1 +1

= a 1 * a 1 * a 1 +(2*k 1 +k 2 ) *a 1 * a 1 +(k 1 *(k 1 +k 2 )+1)*a 1 +1

比较上述三式的同类项，可知命题成立

——思考：

A={a1,a2},B={b1,b2,b3}, 设[A]=[a1 a2]=a1*a2+1 一种值

在运算中{B}={b1,b2,b3}表示三个 顺序 ，即[b1 b2 b3], [b1 b3 b2], [b2 b3 b1]，

若有A<a3<B<a4, 试比较 [[A],a3,{B},a4]与 [[A],a4,{B},a3]

猜测：[[A],a3,{B},a4] > [[A],a4,{B},a3]

因为a3<a4 ，设a4=a3+k , a3=a4-k
[[A],a3,{B},a4]
=[  [A] ,a4-k ,{B} ,a4   ]
= [ [A]*(a4-k)+1 , {B},a4 ]
=[   [ A,a4]-[A]*k ,{B},a4    ]  ——（1）

B={b1,b2,b3} 取任意一个次序
[[A],a3,{B},a4]  ——代入（1）式
=[   [A,a4]-[A]*k ,{ b1, b2,b3,b4},a4    ] 
=[   [A,a4]-[A]*k ,b1, {b2,b3,b4},a4    ] 
= [   ( [A,a4]-[A]*k )*b1+1 , {b2,b3,b4},a4  ]
=[ [A,a4,b1] -[A]*k*b1 , {b2,b3,b4},a4 ]
=.....
= [ [A,a4,b1,b2,b3]-[A]*k*b1*b2*b3 ,a4   ]
=[ [A,a4,b1,b2,b3] *a4 -[A]*k*b1*b2*b3*a4 +1]
=[ [A,a4,b1,b2,b3] *a4 +1 -[A]*k*b1*b2*b3*a4 ]

从结果倒推，找[[A],a4,{B},a3] 形式
aj=ai+k ,a4=a3+k ,
[[A],a3,{B},a4]  
=[ [A,a4,b1,b2,b3] *a4 +1 -[A]*k*b1*b2*b3*a4 ] (上文，代入a4=a3+k)
=[ [A,a4,b1,b2,b3] *(a3+k) +1 -[A]*k*b1*b2*b3*a4 ]
=[ [A,a4,b1,b2,b3] *a3+[A,a4,b1,b2,b3]*k +1 -[A]*k*b1*b2*b3*a4 ]
=[ [A,a4,b1,b2,b3,a3]+[A,a4,b1,b2,b3]*k -[A]*k*b1*b2*b3*a4 ]
=[ [A,a4,b1,b2,b3,a3]+k*( [A,a4,b1,b2,b3] -[A]*b1*b2*b3*a4 ) ]

= [ [A,a4,B,a3+k] +1 - [A]*k*b1*b2*b3*a4 ]
=[ [A,a4,B] *(a3+k)+1 - [A]*k*b1*b2*b3*a4 ]
=[ [A,a4,B] *a3+1+[A,a4,B] *k - [A]*k*b1*b2*b3*a4  ]
=[   [A,a4,B,a3] + [A,a4,B] *k - [A]*k*b1*b2*b3*a4         ]
= [   [A,a4,B,a3] +  k* ( [A,a4,B] - [A]*b1*b2*b3*a4 )        ]
只需比较  [A,a4,B] - [A]*b1*b2*b3*a4  与0
( [A]*a4 +1 )*B+1 -[A]*b1*b2*b3*a4
=展开或者非常显然 >0

因此[[A],a3,{B},a4] >  [[A],a4,{B},a3]

设A={a1,a2...an} 
[A,ai] 
= [{a1,a2,...an} ,ai ]
=[a1,a2,a3...an,ai]
=[ a1*a2+1,a3...an,ai]
=[ ((a1*a2)+1 )*a3+1,....an,ai]
=[ [A],ai ]

(2)假设k=n时命题成立。

即在运算过程中，每次取序列中两个最小值进行运算，最后得到的值为序列的极大值。

令[a i a j ]= a i *a j +1，则数列a的最大极值  {a n}max=[ a1 a2…an ] 。

为了证明k=n+1成立，我们需要先证明一个引理。

——引理

设有数列集合A和B，正整数a i , a j ，且有A<a i < a j <B，

其中，B={b 1 , b 2 , …b m }，{B}表示B中元素的任意组合序列，

则有[ [A] , a i , {B}, a j  ]> [ [A], a j , {B}, a i  ]。

引理证明：第一个表达式 用第二个表达的出来，比较差别

∵ai< aj，∵不妨设aj = ai +k, ai = aj – k // （k>0）

ai = aj – k

[[A], ai, {B}, aj]
= [[A], aj – k, {B}, aj]
= [[A]*(aj – k)+1, {B}, aj]
= [[A]*aj –[A]*k+1, {B}, aj] = [ [A]*aj+1 – [A]*k, {B}, aj]
=[ [A, aj] –[A]*k, {B}, aj]

将B={b1 , b2 , …bm }代入上式，并取B的[任意]一个次序

[[A], ai, B, aj] 
= [[A, aj] –[A]*k, b1 ,{ b2 , …bm}, aj]
= [([A, aj] –[A]*k)*b1 +1,{ b2 , …bm}, aj]
=[ [A, aj] *b1 –[A]*k*b1 +1,{ b2 , …bm}, aj]
= [ [A, aj,b1 ] –[A]*k*b1 ,{ b2 , …bm}, aj]
= [ [A, aj,b1 ,b2 ,…bm] –[A]*k*b1 * b2 *…*bm, aj]
= [ ([A, aj,b1 ,b2 ,…bm]–[A]*k*b1 * b2 *…*bm) * aj +1]
= [ [A, aj,b1 ,b2 ,…bm] * aj–[A]*k*b1 * b2 *…*bm* aj +1]

代入aj = ai +k，B= b1,b2,…bm
[[A], ai, B, aj] 
= [ [A, aj, B] * (ai+k)+1 –[A]*k*b1* b2*…*bm* aj]
= [ [A, aj, B] * ai+1+[A, aj, B] *k –[A]*k*b1* b2*…*bm* aj]
= [ [A, aj, B, ai] +[A, aj, B] *k –[A]*k*b1* b2*…*bm* aj]
= [ [A, aj, B, ai] + k * ([A, aj, B] –[A]*b1* b2*…*bm* aj)]
//证明+的这个  k * ([A, aj, B] –[A]*b1* b2*…*bm* aj)]>0

依据B次序的任意性，可得

[[A], a i ,{B}, a j ] = [ [A, a j , {B}, a i ] + k * ([A, a j , B] –[A]*b 1 * b 2 *…*b m * a j )]

因为[A, a j]=[A]* aj +1，所以[A, a j, B] >[A]*b1 * b2 *…*bm* a j ，//[ A aj B ]= ( [ A ]*aj +1 )*B+1 =[ A ] * aj*B +B +1

则必定有  [[A], a i ,{B}, a j ] > [A, a j , {B}, a i ]

∴引理成立。

引理推广

[{A}, a i ,{B}, a j ] > [{A}, a j , {B}, a i ] 当 [{A}]<a i < a j <[{B}]

A的任意顺序 

引理：[ [A] , ai, {B}, aj ]> [ [A], aj, {B}, ai ]。

根据计算可以得出  [A , ai ] = [  [A], ai ]

但是[ai,A] ！= [ai,[A] ]

比如[ai ,a1,a2]= (ai*a1+1)*a2+1 =ai*a1*a2+ai*a1+a2+1

[ai,[A]]=ai*(a1*a2+1)=ai*a1*a2+ai

【引理】 设有数列集合A和B,正整数a i , a j ,且有[A]<a i < a j <[{B}]，

其中，B={b 1 , b 2 , …b m }，{B}表示B中元素的任意组合序列，则

有[[A], a i , {B}, a j ]> [[A], a j , {B}, a i ]。

可以数字1~4为例，根据引理必有

[[1, 2, 3], 4] > [[1, 2, 4], 3] > [[1, 3, 4], 2] > [[2, 3, 4], 1] //两项同样适用

求证：新加入一个元素 按照数列里最小值优先组合的规则，仍可以得到最大值。

证：前n个步骤得到数列A的第n阶段极大值[A n ]

依据 任意性可知，加入一个新元素  按数列元素最小值优先组合的规则，仍可以得到最大值。则k=n+1时命题成立

计算模型

(1)存储 用数组a[n]来数列

(2)计算

取最小值和第二小值： v min =min{a[n]}, v mins =min{{a[n]}-{v min }}

取最大值和第二大值： v max =max{a[n]}, v maxs =max{{a[n]}-{v max }}

极大值计算：a[v min ]=a[ v min ]*a[ v mins ]+1 //这里vmin是下标

极小值计算：a[v max ]=a[v max ]*a[v maxs ]+1

用最后一个元素覆盖a[ v mins ]或a[v max ] 

代码：

#include<bits/stdc++.h>
using namespace std;
//堆排序 -完全二叉树 
/*01   23  4 5 6 
*/void show(int a[],int n)
{for(int i=0;i<n;i++){cout<<a[i]<<"\t";}cout<<endl<<endl;
}void min_h(int a[],int start,int end)
{//建立父节点指针和子节点指针int f=start;///父节点 int c=f*2+1;//左孩子 int t;//用于交换的临时变量 while(c<=end)//若子节点指针在范围内，进行比较 {//找到最小值的下标 if(c+1<=end && a[c]>a[c+1])//右孩子在范围中，左孩子>右孩子 {c++;}//选中左右孩纸中较小值 //如果父节点 < 子节点 //此时 父<右<左 调整完成 if(a[f]<a[c])return;else//交换 父>右 左>右 ，右是最小的 换到父节点上去 {t=a[f];a[f]=a[c];a[c]=t;f=c;c=f*2+1;}}
}
void min(int a[],int n)
{//初始化 i从最后一个父节点开始调整for(int i=n/2-1;i>=0;i--){min_h(a,i,n-1);} for(int i=n-1;i>0;i--){swap(a[0],a[i]);min_h(a,0,i-1);}
}
int cal(int a[], int n)
{int v1=0,v2=1;while (n > 2){show(a,n);min(a, n);//maxa[v1] = a[v1] * a[v2] + 1;a[v2] = a[n-1];//下次还需排序，因此不用在意顺序，直接将最后一个向前移动n = n - 1;//数目--}//此时n==2return a[0] * a[1] + 1;
}
int main()
{int n = 4;int a[4] = { 8,2,1,3 };cout<<"最大极差：" << cal(a, n);return 0;
}

【例7-3】最优装载。

有一批集装箱准备装上轮船，编号依次 为1, 2, …, n，其中集装箱i的重量是w i，i=1, 2,…, n。已知轮船最 多装载量是C，每个集装箱的重量w i≤C，且对集装箱无体积限 制，设计算法求如何选择能够使得装上的集装箱个数最多。

问题分析

 贪心策略：轻者优先

算法设计与描述	算法分析
输入：	（1）问题输入规模为n
输出：
	（2）选择集装箱是主要工作，时间渐进复杂度T(n)=n （3）排序最快的时间复杂度T(n)=O(nlogn) （4）上述（2）（3）是并列执行的，按照第2章的定理2.2可知时间渐进复杂度T(n)=O(nlogn)

t[]数组存放集装箱的原始编号。通过t 找到x 下标变量

【例7-4】键盘输入

键盘输入一个高精度的正整数N，去掉其中任意

S个数字后剩下的数字按原左右次序将组成一个新的正整

数。对给于定的N和S，寻找一种方案使得剩下的数字组成

的新数最小。

输出：包括所去掉数字的位置和组成的新正整数

 问题分析

(1) 高位的数字尽量小

(2) 删除策略（贪心）：删除高位较大的数字，相邻

两位比较若高位比低位大则删除高位。

(3) 枚举归纳，如当s=3时，输入如下符串：

n1=“1 2 4 3 5 8 6 3”

n2=“2 3 1 1 8 3 1”

n3=“1 2 3 4 5 6 7”

n4=“1 2 0 0 8 3”

=》

n1=“1 2 3 5 3”

n2=“2 1 1 1”        应该是1131 需要回溯，只需向上回溯一位

n3=“1 2 3 4 5 6 7”     应该直接划掉后三个    没删除， 有木有 

n4=“1 0 0 3”        没删够， 有木有

(4) 物理删除：覆盖已删除的字符，字符串长度改变。

 计算模型

(1)存储 a[]存储字数N，data[]记录删除的元素在原

数字中位置；存在一位回溯的操作，设置变量j1来记

住上一次删除的位置。//因为删除，本身位置就变了，不记住，无法找到位置

(2)计算 删除a[i]=a[i+1]，n=n-1。i为数列下标 记录删除位置 //i是几，就删除几次

data[i]=j+i, j1=j, if j≥j1        //不是回溯

data[i] =data[i-1]-1, if j<j1        //回溯位

其中，i为删除次数，j为数列下标

1.删除高位里的大值

2.回溯一位

3.末尾剩几个砍几个

4.高位0

代码：

#include<bits/stdc++.h>
using namespace std;int n = 6;//长度
int s = 3;//要删除的数字个数
char a[] = { '1','2','0','0','8','3' };//数字 
int data[3] = { 0 };//记录删除的元素在原数字中的位置 void show(char a[])
{for(int i=0;i<strlen(a);i++)cout<<a[i]<<'\t';cout<<endl;
}
void del(char a[], int b, int k)//删除,物理覆盖 
{for (int i = b; i < strlen(a); i++){a[i] = a[i + k];}
}
void delD(char a[], int s)
{int i = 0, j = 0, j1 = -1;//存在回溯 int len = strlen(a);//截止到\owhile (i < s && j < strlen(a)){show(a);while (a[j] <= a[j + 1])//一直是前面小 {j++;}//前面大于后面if (j < strlen(a)){//删除a[j]del(a, j, 1);//删除次数 i  if (j >= j1)data[i] = j + i;//删除的第i个元素，在原数组中的位置是j+i else data[i] = data[i - 1] - 1;//回溯，回溯到上一个删除位置 的前一个位置 //j1 = j;i++;j--;if (j < 0)j = 0;}}//显示的时候高位的0不显示 while (a[0] == '0' && strlen(a))		del(a, 0, 1);}int main()
{delD(a, s);cout<<"位置"<<endl;for(int i=0;i<s;i++){cout<<data[i]<<"\t";}cout<<endl<<"新整数";for (int i = 0; i < n-s; i++)cout << a[i];return 0;
}

 近似贪心问题

局部最优 达不到 全局最优