贪心算法-分数背包问题(Fractional Knapsack Problem)和0-1背包问题(0-1 Knapsack Problem)

目录

• • 贪心算法简介
  • 分数背包问题描述
  • 贪心算法求解
  • • 算法简介
    • 算法时间复杂度分析
  • 正确性证明
  • • 交换论证法简介
    • 用交换论证法进行证明
  • 讨论：贪心算法用于0-1背包问题
  • • 最坏结果
    • 改进后的贪心算法用于0-1背包问题

贪心算法简介

贪心算法(greedy algorithm)总是选择当前看来最佳的选择。贪心算法并不总是给出最优解，但它往往是最简单、最高效的算法。

如果贪心算法能给出最优解，它一定要保证每一轮贪心的结果都是一个最优的子结构，即当前的最优解也是全局最优解的一部分。

分数背包问题描述

情景描述：给定背包容量和一些物品，每个物品有重量和价值两个属性。允许只取一个物品的一部分加入背包，求问如何才能使背包装的物品价值最大。

形式化定义：给定

K

K

K和

W

=

(

w

1

,

w

2

,

.

.

.

,

w

n

)

W=(w_1,w_2,…,w_n)

W=(w1​,w2​,…,wn​)，

V

=

(

v

1

,

v

2

,

.

.

.

,

v

n

)

V=(v_1,v_2,…,v_n)

V=(v1​,v2​,…,vn​)。求

X

=

(

x

1

,

x

2

,

.

.

.

,

x

n

)

，

0

≤

x

i

≤

1

X=(x_1,x_2,…,x_n)，0\leq x_i\leq1

X=(x1​,x2​,…,xn​)，0≤xi​≤1，满足

Σ

i

=

0

n

x

i

w

i

≤

K

\Sigma_{i=0}^{n}x_iw_i \leq K

Σi=0n​xi​wi​≤K

使最大化

Σ

i

=

0

n

x

i

v

i

\Sigma_{i=0}^{n}x_iv_i

Σi=0n​xi​vi​

该问题实质上是一个线性规划问题，可以用单纯形法、椭球法、内点法（后两者均为多项式时间算法）等求解。但在这个问题中，简单的贪心算法就能够求出最优解。

贪心算法求解

算法简介

核心思想：按性价比(value-per-pound)排序。

• 计算每个物品的单位重量价格

  ρ

  i

  =

  v

  i

  w

  i

  \rho_i=\frac{v_i}{w_i}

  ρi​=wi​vi​​

• 对

  ρ

  i

  \rho_i

  ρi​的计算结果按降序排序

• 令

  k

  =

  K

  k=K

  k=K，表示当前背包的剩余空间

• 每次都选择物品

  j

  j

  j，它具有当前最高的性价比

  ρ

  j

  \rho_j

  ρj​：

  • 如果

    w

    j

    ≤

    k

    w_j\leq k

    wj​≤k，将重量为

    w

    j

    w_j

    wj​的

    j

    j

    j物品全部加入背包，

    k

    =

    k

    −

    w

    j

    k=k-w_j

    k=k−wj​；

  • 否则将重量为

    k

    k

    k的

    j

    j

    j物品加入背包，迭代结束。

算法时间复杂度分析

• 计算性价比为线性复杂度

  O

  (

  n

  )

  O(n)

  O(n)

• 排序可以选用快速排序、堆排序等算法，时间复杂度为

  O

  (

  n

  l

  o

  g

  n

  )

  O(nlogn)

  O(nlogn)

• 迭代的轮次小于等于

  n

  n

  n，复杂度也为

  O

  (

  n

  )

  O(n)

  O(n)

综上，时间复杂度为

O

(

n

l

o

g

n

)

O(nlogn)

O(nlogn)，可见贪心算法在效率上的优势。

正确性证明

这种选择最高性价比的贪心思想的正确性似乎是显然的，但我们还要进行证明。这里用到的方法是交换论证法(exchange argument)。

交换论证法简介

通常用于证明一个贪心算法给出的解是最优解。大致的思想是先假设一个最优解，再将最优解逐步转化为我们算法给出的解，并保证在转化的过程中结果不变差。如果能够完成转化，那么就可以证明贪心算法给出的解也是最优解。

用交换论证法进行证明

假设已经按照

ρ

i

\rho_i

ρi​进行了排序，即

ρ

1

≥

ρ

2

≥

.

.

.

≥

ρ

n

\rho_1\geq\rho_2\geq…\geq\rho_n

ρ1​≥ρ2​≥…≥ρn​

记贪心算法的解为

G

=

G=

G=。假设一共装了

i

i

i种物品，则根据我们的求解思路，一定有

x

1

,

.

.

.

,

x

i

−

1

=

1

x_1,…,x_{i-1}=1

x1​,…,xi−1​=1，而

x

i

≤

1

x_i\leq 1

xi​≤1。

假设一个最优解

O

=

O=

O=，显然最优解一定也是填满了背包的，即

Σ

y

i

w

i

=

K

\Sigma y_iw_i=K

Σyi​wi​=K。

从下标为

1

1

1开始比较方案

G

G

G和

O

O

O，假设第一个不同的值的下标为

j

j

j，即

x

j

≠

y

j

x_j\neq y_j

xj​=yj​。由于贪心算法的方案每次都尽可能选择最多的量，所以一定有

x

j

≥

y

j

x_j\geq y_j

xj​≥yj​。假设

x

j

x_j

xj​和

y

j

y_j

yj​的不同部分为

δ

j

=

x

j

−

y

j

\delta_j=x_j-y_j

δj​=xj​−yj​，那么由于

Σ

x

i

w

i

=

Σ

y

i

w

i

=

K

\Sigma x_iw_i=\Sigma y_iw_i=K

Σxi​wi​=Σyi​wi​=K，一定有

Σ

k

=

j

+

1

n

y

k

≥

δ

j

\Sigma_{k=j+1}^ny_k\geq\delta_j

Σk=j+1n​yk​≥δj​。那么就可以从

O

O

O的从

j

+

1

j+1

j+1到

n

n

n的物品中凑出

δ

j

\delta_j

δj​的重量重新分配给物品

j

j

j，使得

x

j

=

y

j

+

δ

j

=

y

j

′

x_j=y_j+\delta_j=y’_j

xj​=yj​+δj​=yj′​。由于

ρ

j

≥

ρ

j

+

1

,

.

.

.

,

ρ

n

\rho_j\geq \rho_{j+1},…,\rho_n

ρj​≥ρj+1​,…,ρn​，调整后的

O

′

O’

O′方案一定优于或等于原

O

O

O方案。考虑到

O

O

O方案本来就是最优的，那么

O

O

O和

O

′

O’

O′方案一定是等优越性的。

不断重复以上的步骤，就能将最优的

O

O

O方案等优越性地转化为我们的

G

G

G方案，从而证明了我们的方案也为最优的。

讨论：贪心算法用于0-1背包问题

显然，如果在物品不能分割的情况下（即0-1背包问题），以上的贪心算法不一定给出最优解。因为每一次贪心选择不一定在更全局的最优解中。

最坏结果

一个有趣的问题是，如果一定要用贪心算法来解，结果是可以接受的吗？或者说最坏的结果可以有多坏？

首先，我们确定一个衡量方案优越度的指标：

O

P

T

0

−

1

/

A

OPT_{0-1}/A

OPT0−1​/A

其中，

O

P

T

0

−

1

OPT_{0-1}

OPT0−1​为0-1背包问题的最优解，

A

A

A为其他方案给出的解。这一比值可以衡量方案

A

A

A在一个具体case上的好坏：比值越低，方案越好；如果比值为1，那么方案

A

A

A也为最优解。

考虑如下情况：

K

=

100

K=100

K=100，

W

=

(

100

,

1

)

W=(100,1)

W=(100,1)，

V

=

(

100

,

99

)

V=(100,99)

V=(100,99)，计算得

ρ

=

(

1

,

99

)

\rho=(1,99)

ρ=(1,99)。按选择最高性价比的贪心算法，应该优先选择物品2，但最优解显然是物品1。最极端的情况是物品2的性价比比物品1略高，但总价值远远低于物品1，这样的

O

P

T

0

−

1

/

A

=

∞

OPT_{0-1}/A=\infin

OPT0−1​/A=∞，即最坏情况可以达到任意坏。

改进后的贪心算法用于0-1背包问题

动态规划算法虽然能给出最优解，但在计算效率上远不如贪心算法。能否对贪心算法进行一定的改进，使其在保持效率优越性的情况下保证结果不是太差，比如限制

O

P

T

0

−

1

/

A

≤

2

OPT_{0-1}/A\leq 2

OPT0−1​/A≤2？其实是有的，一个简单的改进如下：

假设分数背包问题中，贪心算法选出

i

i

i种物品加入背包，其中

x

1

,

.

.

.

,

x

i

−

1

=

1

x_1,…,x_{i-1}=1

x1​,…,xi−1​=1，而

x

i

≤

1

x_i\leq 1

xi​≤1。那么在相同的0-1背包问题中，比较物品

1

1

1~

i

−

1

i-1

i−1的总价值和

i

i

i的价值，将更大者加入背包。下面证明

O

P

T

0

−

1

/

A

≤

2

OPT_{0-1}/A\leq 2

OPT0−1​/A≤2：

我们方案的总价值为

A

=

m

a

x

{

Σ

k

=

1

i

v

k

,

v

i

+

1

}

≥

m

a

x

{

Σ

k

=

1

i

x

k

v

k

,

x

i

+

1

v

i

+

1

}

≥

1

2

(

Σ

k

=

1

i

x

k

v

k

+

x

i

+

1

v

i

+

1

)

=

1

2

(

Σ

k

=

1

i

+

1

x

k

v

k

)

≥

1

2

O

P

T

0

−

1

A=max\{\Sigma_{k=1}^i v_k, v_{i+1}\}\geq max\{\Sigma_{k=1}^i x_kv_k, x_{i+1}v_{i+1}\}\geq \frac{1}{2}(\Sigma_{k=1}^i x_kv_k+x_{i+1}v_{i+1})= \frac{1}{2}(\Sigma_{k=1}^{i+1} x_kv_k)\geq \frac{1}{2}OPT_{0-1}

A=max{Σk=1i​vk​,vi+1​}≥max{Σk=1i​xk​vk​,xi+1​vi+1​}≥21​(Σk=1i​xk​vk​+xi+1​vi+1​)=21​(Σk=1i+1​xk​vk​)≥21​OPT0−1​。

说明：倒数第二项即为分数背包问题的最优解。而分数背包问题的最优解总是优于或等于相同的0-1背包问题的最优解。因此总有

A

≥

1

2

O

P

T

0

−

1

A\geq \frac{1}{2}OPT_{0-1}

A≥21​OPT0−1​。

这种近似算法(approximation algorithm)在快速求解复杂问题上往往是很有用的。