算法（五）贪心方法

2021/6/11 1:21:35

编程Tag： 方法算法时间节点作业贪心最优那么期限

本文主要是介绍算法（五）贪心方法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1 背包问题

1.1 题目

在这里插入图片描述

1.2 GREEDY-KNAPSACK算法

太简单了，把单位重量价格贵的往里放就行。
在这里插入图片描述
其中，p是价格，w是重量，x是物品放进去的比例。

1.3 定理5.1

这个证明要求会。
在这里插入图片描述
证明思路：

先设算法所得
解X= (x 1 _1 1,x 2 _2 2,…,x j _j j,…,x n _n n)
如果x都=1，即所有物品都选了，那么一定是最优解。
如果x不都是1，那么设j是第一个≠1的x的下标，即X = (1,1,1,…,1,x j _j j,0,0,0,…,0)。如果X不是最优解，那么一定有一个最优解Y = (y 1 _1 1,y 2 _2 2,……,y n _n n)，使Σp i _i iy i _i i>Σp i _i ix i _i i，设k是x≠y的最小下标，那么有三种情况，证明这三种情况都不正确就可以：
若k<j，这个时候x k _k k=1，假设有y k _k k≠x k _k k，那么y k _k k<x k _k k
若k=j，已经假设y k _k k≠x k _k k，所以只有两种情况。y k _k k>x k _k k时，在X里,Σ i = 1 k ^{k}_{i=1} i=1kp i _i ix i _i i = M(质量上限)，那Σ i = 1 k ^{k}_{i=1} i=1kp i _i iy i _i i肯定 > M，肯定不可能。那就只可能是y k _k k<x k _k k。
若k>j，也有 Σ i = 1 k ^{k}_{i=1} i=1kp i _i iy i _i i > M，矛盾。
发现了吗，上面3中的三种情况，除了Σ i = 1 k ^{k}_{i=1} i=1kp i _i iy i _i i > M这种矛盾情况就是y k _k k<x k _k k，所以我们只要证y k _k k<x k _k k矛盾即可得证。
那么我就将Y中的y k _k k增加到x k _k k那么多，那么一定要将k后面的若干个y——(y k + 1 _{k+1} k+1,y k + 2 _{k+2} k+2,……,y n _n n)中减少相同的质量，假设这个解是Z=(z 1 _1 1,z 2 _2 2,……,z n _n n)。众所周知，前面的贵后面的便宜，贵的质量增加了，便宜的质量减少了（用数学写法表示见图），那Z就一定肯定是更优解。
此时，Z=X那么证明X是最优解，Z≠X只需重复上面的过程（写这几个字就行）直到Z=X即可证X是最优解。

我上面写的这些逻辑关系不太强，所以我补了一个图。
在这里插入图片描述

2 带有限期的作业排序

2.1 GREEDY-JOB算法

经典拿一句汉语伪代码概括一堆代码。
在这里插入图片描述

2.2 定理5.2

证明GREEDY-JOB会得到最优解。

先放书上图：
在这里插入图片描述

设I为最优解，J为贪心解，I=J则J是最优解，I≠J有四种关系：I包含于J，J包含于I，I和J有交集且交集小于I和J，I和J无交集。
说明1：虽然书上和ppt上都说的⊂，但是我觉得⫋更好一点。
说明2：书上后两种合并成一种看，反正就是I和J分别有对方没有的元素。

要注意的一点是，I和J两个集合的元素是包含的作业，不是解集。即I={作业1，作业2，作业3}，J={作业1，作业3，作业4}这种情况，并不是I={解1，解2}这样。

证明：

I ⫋ J：I的效益<J的效益，与最优解矛盾。
J ⫋ I：图为PPT写法，建议按书上写（PPT写的也不是很好我背不下来）：贪心法的工作方式排斥了J⊂I。
第一步：排除了前两种情况，那么一定存在x∈I且x∉J，y∉I且y∈J，设a是满足y的最大的元素，那么a一定大于满足x的所有元素，因为如果a<x那么贪心就会选择x了。
第二步：对于每个I和J中共同包含的作业i，他在I中的执行时间是t，J中的是t’，让t和t’两个时间中更早的时间跟晚一些的时间对齐，如果晚一些的时间已经有作业，那么就将两个作业交换。（如果第四种情况则忽略这步就好了）
举例：对于作业1，I中是时间2，J中是时间3，那么就将I中的作业1放入时间3的位置上（由于J中作业1就在时间3，那么作业1放在时间3是可以的），如果I中时间3本来有作业，那么将作业放到时间2的位置上（向前移是可以的）
第三步：那么现在a对应的时间，在I中相应时间的作业b（或者根本没有作业）的效益一定小于a，那么就将I中此时间改为作业a，不断地重复这个过程会使I不断转化为J，所以J就是最优解。

2.3 定理5.3

在这里插入图片描述
就是说，可行解的充要条件是安排的作业可以按照期限次序递增(δ)处理而又不违反任何一个期限。
注意这里是说“可以按照”，不代表可行解一定是期限递增，但可以重排序按照期限递增的方式处理作业。

证明：

安排的作业可以按照期限递增处理又不违反任何一个期限，那显而易见这是一个可行解。
δ是递增序列（元素是i），δ’是J中使用的序列（元素是r），找到第一个不同的作业r a _a a≠i a _a a，找到递增序列δ这个位置的作业i a _a a在J序列δ’中的位置r b _b b，r b _b b=i a _a a，交换J序列中的r a _a a和r b _b b（因为d r a _{ra} ra=d r b _{rb} rb所以可交换），不停如此交换可以从δ’转化为δ，得证。

2.4 JS算法

我看了半天才看明白，非常简单。作业是按效益降序排列的，J中先放作业1，然后每次考虑一个作业从头到尾是否有一个点可以插入，使后面的每一个作业往后移一位且都还合法，找到这样的第一个点，如果找不到就不插入了。
在这里插入图片描述

2.5 FJS算法

开始犯病了，J是最优解，p（小写）是降序排列的效益，D是对应的期限没变，P（大写）变成了树的父亲节点（parent），b是时间片的数量。在定义里，F是这个时间及以前最接近的空时间片，但是实际是这个时间的P祖宗的F才是（后面还会提及到）。

看着代码理解一下，主要要会后面的画图。