与动态规划相同贪心算法通过做出一系列选择来构建出问题的最优解,不同的是贪心算法
并不会全局考虑各种选择,它只做当前看起来最佳的选择。如君所见,贪心算法企图用每
一步的最优解来构建出整个问题的最优解。这并不能保证总能构建出最优解,但它通常能
做到。我们可以先看一个具体的问题——活动安排问题。

活动安排问题

有一系列活动\( S = {a_1, a_2, \dots, a_n} \),它们都要用到同一个舞台,而
舞台一次只能举办一个活动。那么要如何安排才能举办最多的活动呢?

假设活动\(a_i\)的开始时间用\(s_i\)表示,结束时间用\( f_i \)表示, 有
\( 0 \leq s_i < f_i < \infty \). 也就是说\( a_i \)占用舞台的时间段为
\( [s_i, f_i] \)。那么安排的活动之间必须满足一个条件,那就是各自的时间段之
间没有重叠的部分。

一个具体的例子(将这些活动按结束时间排好了序):

i1234567891011
\(s_i\)130535688212
\(f_i\)4567991011121416

对于这样一个问题,因为能够比较快速的发现其最优子结构,我们会很容易想到用动态规
划来解决。——假设\(a_i\)是最优解中的一个元素,那么以\(a_i\)为界可以将问题
分成为两个子问题,一个是活动结束时间在\(a_i\)的开始时间之前的所有活动,另一个
则是活动开始时间在\(a_i\)结束时间之后的所有活动。可以证明最优解包含这两个子问
题的最优解组成的,具体证明可见原书。

令\( S_{ij} \)代表活动开始时间在\(a_i\)结束之后而活动结束时间在\(aj\)
开始之前的所有活动的集合,用\( c[i, j] \)来代表的\(S
{ij}\)的最优解,那么
我们可以获得递归公式:

如果用贪心算法的话,则不用考虑那么多种选择,只需考虑贪心选择——当前最佳的选择。
在这个问题上,我们可以总是优先安排结束时间最早而又不与之前安排的任务有冲突的活
动,这即是一种贪心选择。但最大的问题在于贪心选择是否是最佳选择?在这里,确实是
的,你可以用算导中提到的“粘贴替代”的方法轻易的证明。

迭代与递归两种版本的伪码

递归版:

1
2
3
4
5
6
RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)
m = k + 1
while m <= n and s[m] < f[k]
m = m + 1
if m <= n
return {a<sub>m</sub>} ∪ RECURSIVE-ACTIVITY-SELECOR(s, f, m ,n)

迭代版:

1
2
3
4
5
6
7
8
9
GREEDY-ACTIVITY-SELECTOR(s, f)
n = s.lenght
A = {a<sub>i</sub>}
k = 1
for m = 2 to n
if s[s] > = f[k]
A = A ∪ {a<sub>m</sub>}
k = m
return A

C++的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename Container> 
int greedy_activity_selector(Container input, Container& result)
{
//*input 应当是一个容器,每个元素为一个pair对,
//*每个pair对包含一个活动的开始时间和结束时间
result.clear();
auto a=input.begin(); //a 存储贪心选择;
result.push_back(*a);
auto iter=a;
++iter;
while(iter!=input.end())
{
if(iter->first >= a->second)
{
result.push_back(*iter);
a=iter;
}
++iter;
}
return result.size();
}

贪心算法的基本内容

贪心算法并不能解决所有最优解问题。

贪心选择性质(greedy-choice property)和最优子结构(optimal substructure)是贪心算
法的两个关键点。如果一个问题具备以上两种属性,那么就能设计出适合这个问题的贪心
算法。

greedy-choice property: we can assemble a globally optimal
solution by making a locally optimal (greedy) choice. In other words,
when we are considering which choice to make, we make the choice that
looks best in the current problem, without considering results from
subproblems.

贪心策略VS动态规划

就动态规划来说,我们在每一步做出选择,但是这些选择往往会依赖与子问题的解。而贪心
算法,总是做出当前看似最佳的选择,它可能会依赖于之前做过的选择,但绝不会依赖于尚
未做出的选择或者子问题。一次动态规划通常采用自下而上的方式,不断解决小问题以供大
问题使用,而贪心算法则采用自顶而下的方式不断缩小问题的规模。

一般来讲,对于一个有贪心策略解法的问题,也常常有一个更复杂的动态规划解法。也由于
动态规划和贪心策略都利用了最优子结构这一性质,往往容易在贪心算法足以解决问题的情
况小使用了动态规划。或者在需要动态规划解决的地方使用贪心策略,这需要我们自行甄别。

0-1背包和部分背包问题

The 0-1 knapsack problem is the following. A thief robbing a
store finds n items; the ith item is worth \( v_i \) dollars
and weighs \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers.
He wants to take as valuable a load as possible, but he can carry at
most W pounds in his knapsack for some integer W. Which items should
he take? (This is called the 0-1 knapsack problem because each item must
either be taken or left behind; the thief cannot take a fractional
amount of an item or take an item more than once.)

In the fractional knapsack problem, the setup is the same, but
the thief can take fractions of items, rather than having to make a
binary (0-1) choice for each item. You can think of an item in the 0-1
knapsack problem as being like a gold ingot, while an item in the
fractional knapsack problem is more like gold dust.

两个背包问题都有最优子结构,但0-1背包不能用贪心策略来解决,而部分背包可以。对于部
分背包来说,因为可以只拿部分,所以不用考虑背包会不会不能塞满,所以总是先拿剩余物品
中每镑最值钱的东西会导致全局最优解。而0-1背包则不然,因为物体不能只拿部分,所以可
能会导致背包不能完全被利用。下图为一个实例。

图解: The greedy strategy does not work for the 0-1 knapsack problem.
(a) The thief must select a subset of the three items shown whose
weight must not exceed 50 pounds. (b) The optimal subset includes
items 2 and 3. Any solution with item 1 is suboptimal, even though
item 1 has the greatest value per pound. (c) For the fractional
knapsack problem, taking the items in order of greatest value per
pound yields an optimal solution.

0-1背包不能用贪心策略来求解,但动态规划确实使用它的。

参考: introduction to algorithm –third edition