贪心算法之部分背包问题
一.题目描述
假设山洞中有 n 种宝物，每种宝物有一定重量w 和相应的价值v，毛驴运载能力有限，只能运走 m 重量的宝物，一种宝物只能拿一样且宝物可以分割，如何使毛驴运走的宝物价值最大化？
Input：输入毛驴可承受的最大重量m，若干个宝物重量w和他们的价值v
Output：输出能运走的最大价值
与不同，此处的物品是可以分割的，所以叫做部分背包问题
二.解题思路
1. 首先设计贪心策略：
(1) 若每次挑选价值最大的宝物装入背包，得到的结果是否最优？
(2) 若每次挑选重量最小的宝物装入背包，得到的结果是否最优？
(3) 每次挑选单位重量价值(性价比)最大的宝物装入背包，得到的结果是否最优？
由于一种宝物只能拿一样且宝物可以分割，所以选择策略(3)能得到最大价值。
2. 实现贪心策略
(1) 计算出每件宝物的性价比，按照从高到低排序；
(2) 根据贪心策略，按性价比从大到小选取宝物，直到达到毛驴儿的运载能力。
(3) 每次选择宝物后判断总重量是否小于m，是则装入。
三.编程实现
datas = [
[2, 1],
[3, 3],
[4, 5],
[7, 9]]
m = 30 # 毛驴的运载能力
w = 0 # 获取的总价值
for i in range(len(datas)):
price = datas[i][1] / datas[i][0]
datas[i].append(price)
datas.sort(key=lambda data: data[2], reverse=True)
for data in datas:
if data[0] <= m:
w += data[1]
m -= data[0]
else:
w += data[2] * m
print("能运走的最大价值：%.2f" % w)END
往期回顾