博客

对于背包问题可以用贪心算法求解，作为01背包的上界函数

下面证明背包问题满足贪心选择性质：

设有一按照

单位价值排序好

的最优解T=(tk,….tn)

第一个装入的物品是tk

若k=1

则存在贪心性质出发的最优解

若k不等于1：

如果物品k比物品1重，将k物品中物品1重量的

部分卸下

，换成物品1,构造新的解T’，

满足容量约束

，且背包

价值优于T

如果物品1比k重，则将k卸下，装上1物品的一部分（与物品k同样重量），满足容量约束，且背包价值优于T

因此总存在以

贪心性质开始

的最优解，由

数学归纳法

可以得到满足贪心性质的最优解。