贪心算法与动态规划的比较

【

摘

 

 

要

】介绍了计算机算法设计的两种常用算法思想：

 

贪心算法与动态规划算法。通过

介绍两种算法思想的基本原理，

比较两种算法的联系和区别。

通过背包问题对比了两种算法

的使用特点和使用范围。

 

【

关键字

】动态规划；贪心算法；

 

背包问题

 

 

 

1

、引言

 

 

 

 

 

为了满足人们对大数据量信息处理的渴望，

为解决各种实际问题，

计算机算法学得到了

飞速的发展，

线性规划、

动态规划、

贪心策略等一系列运筹学模型纷纷运用到计算机算法学

中，

产生了解决各种现实问题的有效算法。

虽然设计一个好的求解算法更像是一门艺术而不

像是技术，

但仍然存在一些行之有效的、

能够用于解决许多问题的算法设计方法，

你可以使

用这些方法来设计算法，

并观察这些算法是如何工作的。

一般情况下，

为了获得较好的性能，

必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，

这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和

0/ 

1 

背包问题进行分

析，介绍贪心算法和动态规划算法的区别。

 

2

、背包问题的提出

 

 

 

 

 

给定

n

种物品

( 

每种物品仅有一件

) 

和一个背包。物品

i

的重量是

w

 

i

 

，其价值为

p 

i

 

，

背包的容量为

M

。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大

,

每件

物品

i

的装入情况为

x

 i

，得到的效益是

p 

i

*x 

i

 

。

 

 

 

 

 

⑴部分背包问题。在选择物品时，可以将物品分割为部分装入背包，即

0

≤

 

x 

i

 

≤

1 ( 

贪心

算法

)

。

 

⑵

 

0/ 

1

背包问题。和部分背包问题相似，但是在选择物品装入时要么不装，要么全装

入，即

x

 i

 = 1

或

0

。

( 

动态规划算法

) 

。

 

3

、贪心算法

 

3.1 

贪心算法的基本要素

 

 

 

 

 

能够使用贪心算法的许多例子都是最优化问题，

每个最优化问题都包含一组限制条件和

一个优化函数，

符合限制条件的问题求解方案称为可行解；

使优化函数取得最佳值的可行解

称为最优解。

此类所求问题的整体最优解可以通过一系列局部最优的选择，

即贪心选择来达

到

(

这是贪心算法与动态规划的主要区别

) 

。

 

 

3.2

 

贪心策略的定义

 

 

 

 

 

贪心策略是指从问题的初始状态出发，

通过若干次的贪心选择而得出最优值

( 

或较优解

) 

的一种解题方法。

贪心策略总是做出在当前看来是最优的选择，

也就是说贪心策略并不是从

整体上加以考虑，

它所做出的选择只是在某种意义上的局部最优解，

而许多问题自身的特性

决定了该问题运用贪心策略可以得到最优解或较优解。

(

注：贪心算法不是对所有问题都能

得到整体最优解，

但对范围相当广泛的许多问题它能产生整体最优解。

但其解必然是最优解

的很好近似解。

) 

 

 

 

 

采用自顶向下的、

以迭代的方法做出相继的贪心选择，

每做一次贪心选择就将所求问题

简化为一个规模更小的子问题。

对于一个具体问题，

要确定它是否具有贪心选择的性质，

我

们必须证明每一步所作的贪心选择最终导致问题的最优解。

通常可以首先证明问题的一个整

体最优解，

是从贪心选择开始的，

而且作了贪心选择后，

原问题简化为一个规模更小的类似

子问题。

然后用数学归纳法证明，

通过每一步贪心选择，

最终可得到问题的一个整体最优解。

 

3

、

3

贪心算法的实际应用例子

 

⑴贪心法的基本思路。

 

从问题的某一个初始解出发逐步逼近给定的目标，

以尽可能快地求得更好的解。

当达到

某算法中的某一步不能再继续前进时，算法停止。

 

⑵该算法存在的问题。

 

①

 

不能保证求得的最后解是最佳的；

 

②

 

不能用来求最大或最小解问题；只能求满足某些约束条件的可行解的范围。

 

⑶实现该算法的过程。

 

从问题的某一初始解出发；

 

当能朝给定总目标前进一步时，求出可行解的一个解元素；

 

由所有解元素组合成问题的一个可行解。

 

    

⑷背包问题分析实例（部分背包问题）

。有一个背包

,

容量是

M = 150

，有

7

个物品，物

品可以分割成任意大小，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

 

其重量和价值如下。

 

物品

 

A 

 

 

B 

 

 

C 

 

 

D 

 

 

E 

 

 

F 

 

 

G 

重量

 

35 

 

30 

 

60 

 

50 

 

40 

 

10 

 

25 

价值

 

10 

 

40 

 

30 

 

50 

 

35 

 

40 

 

30 

 

 

 

 

其中目标函

i

p



最大。约束条件是装入的物品总重量不超过背包容量：

 

i

w



< M

（

M=150) 

根据贪心的策略，每次选取单位容量价值最大的物品

,

成为解本题的策略。可以证明得

到最优解为

x = [ 0

，

1

，

0

，

1

，

7

/ 8

，

1

，

1]

总价值为：

190. 6

。

 

3

、

4 

贪心算法不适于解

0/ 1 

背包问题

 

 

 

 

 

0/ 

1 

背包问题有好几种贪婪策略，每种贪婪策略都要多个步骤来完成，每一步都利用

贪婪准则选择一个物品装入背包。

一种贪婪准则为：

从剩余的物品中，

选出可以装入背包的

价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量）

，然后是

下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑

n= 2

，

 

w = [ 100

，

10

，

10] 

，

 

p = [ 20

，

15

，

15] 

，

c = 105

。当利用价值贪婪准则时，获得的解为

x = 

[ 

1

，

0

，

0] 

，这种方案的总价值为

20

。而最优解为

[ 

0

，

1

，

1] 

，其总价值为

30

。另一种方

案是重量贪婪准则：

 

从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对

于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑

n =2

，

w =[ 10

，

20] 

，

p = [ 5

，

100] 

，

c = 25

。

当利用重量贪婪策略时，

获得的解为

x = [ 1

，

0] 

，

比最优解

[ 0

，

1] 

要差。还可以利用另一方案，价值密度

p 

i

 / w

i

贪婪算法，这种选择准则为：从剩余物品

中选择可装入包的

p 

i

 / w

i

值最大的物品，这种策略也不能保证得到最优解。

 

4

、动态规划

 

4

、

1 

动态规划的定义

 

 

 

 

 

动态规划是运筹学的一个分支，

与其说它是一种算法，

不如说它是一种思维方法更贴切。

因为动态规划没有固定的框架，

即便是应用到同一道题上，

也可以建立多种形式的求解算法。

许多隐式图上的算法，例如求单源最短路径的

Dijkstra 

算法、广度优先搜索算法，都渗透着

动态规划的思想。

还有许多数学问题，

表面上看起来与动态规划风马牛不相及，

但是其求解

思想与动态规划是完全一致的。

因此，

动态规划不像深度或广度优先那样可以提供一套模式，

需要的时候，取来就可以使用。

它必须对具体问题进行具体分析、

处理，需要丰富的想象力

去建立模型，需要创造性的思想去求解。

 

4

、

2 

动态规划适于解决的问题

 

 

 

 

 

适用动态规划的问题必须满足最优化原理和无后效性。

 

⑴状态必须满足最优化原理。

作为整个过程的最优策略具有如下性质：

无论过去的状态

和决策如何，

对前面的决策所形成的当前状态而言，

余下的诸决策必须构成最优策略。

可以

通俗地理解为子问题的局部最优将导致整个问题的全局最优，

即问题具有最优子结构的性质，

也就是说一个问题的最优解只取决于其子问题的最优解，非最优解对问题的求解没有影响。

 

⑵状态必须满足无后效性。

所谓无后效性是指：

过去的决策只能通过当前状态影响未来

的发展，

当前的状态是对以往决策的总结。

它说明动态规划适于解决当前决策和过去状态无

关的问题。

状态出现在策略的任何一个位置，

它的地位都是相同的，

都可以实施同样的决策，

这就是无后效性的内涵。

 

4

、

3

动态规划问题的特征

 

 

 

 

 

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：

最优子结构性质和子问

题重叠性质。

 

 

 

 

 

①

 

最优子结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结

构性质。

 

 

 

 

 

②

 

重叠子问题。

在用递归算法自顶向下解问题时，

每次产生的子问题并不总是新问题，

有些子问题被反复计算多次。

动态规划算法正是利用了这种子问题的重叠性质，

对每一个子

问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。

 

4

、

4

设计动态规划法的步骤

 

⑴找出最优解的性质，并刻画其结构特征；

 

⑵递归地定义最优值

( 

写出动态规划方程

) 

；

 

⑶

 

以自底向上的方式计算出最优值；

  

⑷根据计算最优值时得到的信息，构造一个最优解。

 

步骤

1- 3 

是动态规划算法的基本步骤。

在只需求出最优值的情形下，

步骤

4 

可以省略，

步骤

3 

中记录的信息也较少；

若需要求出问题的一个最优解，

则必须执行步骤

4

，

步骤

3 

中

记录的信息必须足够多，以便构造最优解。

 

4

、

5

动态规划算法

 

 

 

 

 

[ 0/ 1 

背包问题

] 

 

在该问题中需要决定

n

x

x

,......,

1

 

的值。假设按

i=1

，

2

，

......

，

n

的次

序来确定

x

i

 

的值。如果置

x

1

= 

0

，则问题转变为相对于其余物品（即物品

2

，

3

，

......

，

n

）

，

背包容量仍为

c

的背包问题。若置

x

1

=1

，问题就变为关于最大背包容量为

c-w

1

的问题。现

设

r& Icirc

；

{c-w

1

}

为剩余的背包容量。在第一次决策之后，剩下的问题便是考虑背包容量为

r

时的决策。不管

x

i

 

是

0 

或是

1

，

[x

2

，

......

，

x

n

] 

必须是第一次决策之后的一个最优方案，

如果不是，则会有一个更好的方案

[y

2

，

......

，

y

n

]

，因而

[x

1

，

y

2

，

......

，

y

n

] 

 

是一个更好的方

案。

 

 

 

 

 

假设

n=3

，

w=[ 100

，

14

，

10] 

，

p=[ 20

，

18

，

15]

，

c=116 

。若设

x

1

==1 

，则在本次决策