背包问题的贪心算法.pdf

11S103001 郝亚峰 2 班 第八次算法作业 Greedy 算法练习： 问题：背包问题，定义如下： 输入：正数P , P , …, P ; W , W , …, W ; M 1 2 n 1 2 n 输出：X , X , …, X , 0 ≤X ≤1, 使得： 1 2 n i  P X 最大 i i 1in W X  M i i 1in 给出一个求解背包问题的贪心算法，并证明算法的正确性。 解答：我们采用两种思路来求解这个问题，一个是求解贪心算法的一般方法，证明贪心 选择性，优化子结构，给出贪心算法，证明算法的正确性和给出复杂度分析；另一个就是将 该问题转化为拟阵，利用求解拟阵来的贪心算法来求解该问题。 对问题简单的分析：原来的0/1 背包问题是一件物品要么全拿，要么不拿，而这问题则 是可以拿物品的一部分，P 表示物品 i 的价值，W 表示物品 i 的重量，X 表示取物品 i 的百 i i i 分比。 方法一 1、贪心选择方法：我们根据输入的序列构造一个新的序列：P /W , P /W , …, P /W ；这序 1 1 2 2 n n 列表示的含义是每件物品单位重量的价值；我们对这个序列进行从大到小排序，按照这 个排序进行选择物品装入包中，直到包装满为止，对于最后一件物品可能不能完全装入， 只能装入一部分。 2、贪心选择性证明：假设序列P /W , P /W , …, P /W 从大到小排序后的第一个值的下标为 1 1 2 2 n n k，表示物品k 的单位重量的价值最大，那么我们要证明的是存在一个最优解A 包含X ， k 并且若M≥W ，则X =1；否则X =M/W 。 k k k k 证明：假设B 是问题的一个最优解，如果B 包含X ，且满足 “若 M≥W ，则X =1；否 k k k 则X =M/W ”，那么令A=B ，B 就是我们所要寻找的最优解，问题得证。否则，如果B 中 k k 不包含X 或者是如果 B 包含X 但是不满足 “若 M≥W ，则X =1 ；否则X =M/W ”，可 k k k k