贪心算法 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
