部分背包问题

贪心算法 Python

问题描述：给定n个物品，物品价值分别为$P_1$，$P_2$，$...$，$P_n$，物品重量分别为$W_1$，$W_2$，$...$，$W_n$，背包容量为$M$。每种物品可部分装入到背包中。输出$X_1$，$X_2$，$...$，$X_n$，$0\leq X_i\leq1$,使得$\sum_{1\leq i\leq n}P_iX_i$最大，且$\sum_{1\leq i\leq n}W_iX_i\leq M$。设计一个算法求解该问题，分析算法的正确性。

采用贪心策略求解，因为我们可以根据每个物品的单位重量价值进行比较，优先选择单位重量下价值最大的物品，直到某一物品拿了部分或拿完后背包达到了最大重量。可以证明该算法的正确性:

① 通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
② 原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。

具体算法代码如下

def fractional_kanpsack(W,wt,val,n):
    # 对所有物品根据单位重量价值排序
    s = dict([(i,(float)(val[i])/wt[i]) for i in range(n)])
    seq = sorted(s.iteritems(),key=lambda e:e[1],reverse=True)
    rest = W
    result = [0]*n
    # 每次讲单位重量价值最大的物品放入背包，直到背包放不下任何物品
    for j in range(len(seq)):
        if rest >= wt[seq[j][0]]:
            result[seq[j][0]] = wt[seq[j][0]]
            rest = rest - wt[seq[j][0]]
        else:
            result[seq[j][0]] = rest
            rest = 0
    return result

def greedy_benefit(result,val):
    # 计算贪心策略的最大价值
    benefit = 0
    for i in range(len(val)):
        benefit += result[i]*val[i]
    return benefit