赞
踩
下一次输入为使得效益值加最增大的作业,同时不违反约束条件。
max
∑
i
∈
J
p
i
\max \sum_{i\in J}{p_i}
maxi∈J∑pi
procedure GREEDY_JOB(D, J, n)
// 作业按 p1 ≥ p2 ≥ … ≥ pn的次序输入,它们的期限值 D(i) ≥ 1, 1 ≤ i ≤ n, n ≥ 1。
// J是在它们的截止期限完成的作业的集合
J←{1}
for i←2 to n do
if J∪{i}的所有作业能在它们的截止期限前完成 then
J←J∪{i}
endif
repeat
end GREEDY_JOB
设最优解集合为I,贪心解集合为J
若I==J,则贪心解就是最优解
若I!=J,则分三种情况:
2.1 I ⊂ \subset ⊂J
X
若贪心解包含最优解,则最优解至少还能够添加J中有而I中没有的元素且不违反约束条件,这与它本身就是最优解相矛盾。因此这种情况不可能。
2.2 J ⊂ \subset ⊂I
X
若最优解包含贪心解,因为贪心解每次选择总是选择效益值较大且满足约束条件的,故对于I中有而J中没有的元素x,x总应该被J选中才满足贪心算法的规则。因此这种情况不可能。
2.3 I与J中至少包含一个互不相同的元素
√
排除了2.1、2.2两种情况,最后一种情况只剩I
⊄
\not\subset
⊂J
且J
⊄
\not\subset
⊂I
,即至少存在两个作业a和b,使得a
∈
\in
∈J
且a
∉
\not\in
∈I
,b
∈
\in
∈I
且b
∉
\not\in
∈J
。并设a
是这样的一个具有最高效益值的作业,且由算法的处理规则可得:对于在I
中而不在J
中的所有作业b
,有:
p
a
⩾
p
b
p_a\geqslant p_b
pa⩾pb
证明:将I
和J
中的所有作业按效益值非递增排序,从左向右依次比较I
和J
中对应的分量,若相同则继续比较下一个,直至遇到分量不同的情况。设此时两分量为
p
a
p_a
pa和
p
b
p_b
pb。这时若
p
a
<
p
b
p_a<p_b
pa<pb,则不满足贪心算法的规则。贪心算法在下一次选择时,必定会选择效益值相对较大且不违反约束条件的,若
p
a
<
p
b
p_a<p_b
pa<pb,则贪心算法应该选择
p
b
p_b
pb才对。证毕。
使用贪心解分量替换最优解对应分量
3.1 首先调整最优解和贪心解中作业的位置,使得新的解仍能够满足约束条件。设i
在贪心解中和在最优解中都有这个作业,且在贪心解中[t, t+1]
时间段内执行,在最优解中[t', t'+1]
时间段内执行。下面分两种情况进行作业对换:
3.2 找到Pa
在贪心解中的位置,把最优解中对应位置的Pb
替换为Pa
,则替换后的解不会比原来的解更差,且新的解和原来的最优解相比,减少了1个和贪心解不同的元素。如此往复,知道贪心解完全替换最优解,效益值并没有减小。因此,J
也是最优解。
给定一个解,判断这个解是否可以满足约束条件。
下面证明:
证明:
左到右:显然成立
右到左:
procedure JS(D,J,n,k) // D(1),…,D(n)是期限值。n≥1。 // 作业已按p1 ≥ p2 ≥ … ≥ pn的顺序排序。 // J(i)是最优解中的第i个作业,1 ≤ i ≤ k。 // 终止时, D( J(i) ) ≤ D( J(i+1) ), 1 ≤ i<k。 integer D(0:n),J(0:n),i,k,n,r D(0)←J(0)←0 //初始化// J(1)←1; k←1 //计入作业1// for i←2 to n do //按p的非增次序考虑作业。找i的位置并检查插入的可行性// r←k while D(J(r))>D(i) and D(J(r)) ≠r do // r之前的期限比i晚 and r之前的期限可以后移1单位期限 r←r-1 repeat if D(J(r)) ≤ D(i) and D(i)>r then // i的期限比r晚 and i的期限满足约束条件 for i←k to r+1 by -1 do J(i+1) ←J(i) //将插入点的作业后移一位// repeat J(r+1) ←i;k←k+1 endif repeat end JS
#include <iostream> void JS(int D[], int J[], int n) { int cnt = 0; // 最优解中作业数量 // J[i]: 最优解中第i个作业 // D[i]: 作业i的截止期限, 假设作业已经按效益值从大到小排列 // 初始化 D[0] = 0; J[0] = 0; J[1] = 1; // 第1个作业肯定是作业1 cnt = 1; for (int i = 2; i <= n; ++i) { int r = cnt; // D[J[r]] > D[i] 第J[r]个作业的期限大于第i个作业的期限 // D[J[r]] != r 保证第J[r]个作业能往后移动1位 while (D[J[r]] > D[i] && D[J[r]] != r) r--; // 第i个作业要插到r后 // D[i] >= D[J[r]] 第i个作业的截止期限大于等于最优解中第r个作业的截止期限 // D[i] > r 第i个作业的截止期限大于r(能被安排到第r之后) if (D[i] >= D[J[r]] && D[i] > r) { // r之后的最优解往后移1位 for (int j = cnt; j > r; --j) { J[j + 1] = J[j]; } // 插入i J[r + 1] = i; cnt++; } } } int main() { int n = 5; int D[] = {0, 2, 1, 2, 1}; int P[] = {0, 100, 20, 15, 10}; int* J = new int[n]; for (int i = 0; i < n; ++i) { J[i] = 0; } JS(D, J, n); std::cout << "决策序列:"; int sum = 0; for (int i = 1; i < n; ++i) { std::cout << J[i] << " "; sum += P[J[i]]; } std::cout << std::endl << "总效益值:" << sum << std::endl; return 0; }
输出:
决策序列:2 1 0 0
总效益值:120
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。