背包问题

来自计算思维百科
跳转至: 导航搜索
背包问题1.png

背包的最大容量有限,每件物品都有自己的价值和重量,怎样选择物品放入背包中使得背包内物品的总价值最大。

解决方案

背包问题(Knapsack problem)由Merkel和Hellman在1978年提出。我们可以用这样一个场景来生动地描述:小偷在屋子里偷东西,他带着一只背包。屋子里物品数量有限,并且每种物品都只有一件,每件物品都具有一定的重量和价值,比如珠宝重量轻但价值高,桌子重但价值低,那么小偷要拿什么东西既能使背包装得下,而且最值钱?要解决这个问题,我们当然可以用蛮力法,将所有可能的装包方式都列出,一一计算每种方式背包重量以及价值然后选出最合适的。但是,可想而知,效率低下。这里主要介绍使用动态规划算法来解决此问题。

假设背包容量为2.5kg,有4个物品,物品重量和价值如下表所示,

物品

重量(kg)

价值(元)

手机

1

2400

手表

0.5

2000

单反

1.5

4000

首饰

1

3000

我们不要一次性考虑所有的物品,可以一个一个考虑是否要装这个物品,装了之后背包能不能承受,并且价值会不会上升,也就是我们要比较:如果不放入当前物品,该重量的最大价值;如果放入当前物品,当前物品的价值 + 可以容纳的剩余重量的价值,这两个选择的价值大小。

根据这个思想,我们可以构造如下的动态规划表:

背包容量

总价值

物品

0

0.5

1

1.5

2

2.5

没有

0

0

0

0

0

0

手机

0

0

2400

2400

2400

2400

手表

0

2000

2400

4400

4400

4400

单反

0

2000

2400

4400

6000

6400

首饰

0

2000

3000

5000

6000

7700

对于表格中V[i,j](第i行第j列)的值,我们可以根据一个递推式得到:

表格第i行第j行的价值背包问题2.png ,其中vi表示第i个物品的价值,wi表示第i个物品的重量。 V[i-1,j]就是 不放入当前物品,该重量的最大价值,Vi+V[i-1,j-wi]就是当前物品的价值 + 可以容纳的剩余重量的价值。

应用案例

应用1-货物装载

案例:在家具店中4种不同的货物。现将货物装车,规定从每种货物中最多只能拿一件,车子的容量为500,物品占用空间及价值如下表所示。现要使车中装载的物品价值最大,要怎样装货呢?当然,所装货物不能超过车的容量,且同一种物品不得拿走多件。

货物

占用空间

价值(元)

书桌

200

400

椅子

100

200

冰箱

300

1000

空调

200

600

解决步骤: 构造动态规划表如下,

货车容量

总价值

货物

0

100

200

300

400

500

没有

0

0

0

0

0

0

书桌

0

0

400

400

400

400

椅子

0

200

400

600

600

600

冰箱

0

200

400

1000

1200

1400

空调

0

200

600

1000

1200

1600

应用2-旅游行程安排

案例:小红有一个10天的假期,现有4个旅游景点的游玩天数以及推荐值如下表,她要怎么选择,使得总共的游玩天数不超过15天,并且推荐值最高?

景点

游玩天数

推荐值

丽江

8

100

桂林

4

60

厦门

2

40

重庆

6

80

解决步骤:

构造动态规划表如下:

游玩天数

推荐值

景点

0

2

4

6

8

10

没有

0

0

0

0

0

0

丽江

0

0

0

0

100

100

桂林

0

0

60

60

100

100

厦门

0

40

60

100

100

140

重庆

0

40

60

100

120

140

根据上面的动态规划表格,可知小红应该去重庆和桂林。

可以体现的计算思维

运用动态规划表格中计算过的价值来帮助计算当前价值,使问题得到最优解。动态规划解决背包问题体现了计算思维的“规划”特点。