博客

最近复习了一下算法，觉得背包问题最具代表性。可以用大多数通用的算法（穷举，动规，回溯，分枝限界）来解决。因此将最近的笔记整理一下，发到自己的博客上。

问题描述：背包的容量为

C

，现有N件物品，价格分别为

p[0],p[1]……p[n-1].

重量分别为：

w[0],w[1]……w[n-1].

从N件物品中选择任意个放入背包中，使得物体的价值最大并且总重量不超过背包的容量C。

采用数学语言描述如下：

在

w[0]*x[0] + w[1] *x[1]+……. +w[n-1]*x[n-1]  < C, x[i] = 0 或1

的条件下

求

p[0]*x[0] + p[1] *x[1]+……. +p[n-1]*x[n-1]

的最大值。

穷举算法的基本思想如下：

枚举也所有可能的情况，找出其中的最大值。

用N位二进制数来表示N件物品的选取情况，例如在N＝3的情况下 ‘000’代表未选取任何物品，而 ‘101’代表选取了第1件和第3件物品。因此将 0 —- 2^n-1 的情况枚举，找也最大值即可。

算法如下：