0-1背包问题（1）：贪心算法
问题：
有 n 个物品和背包的容量，每个物品的重量为 w[i]，价值为 v[i]，背包的容量为 W。选若干个物品放入购物车，物品不可分割，使价值最大。
问题分析：
首先考虑贪心策略：
- 每次挑选价值最大的物品放入背包
- 每次挑选重量最小的物品放入背包
- 每次挑选单位价值最大的物品放入背包
思考一下，如果选择价值很大的物品，但重量非常大，也是不可行的，策略 1 舍弃；如果选择重量很小的物品，但是价值很小，也是不行的，策略 2 舍弃；策略 3 是每次选择单位价值最大的物品，也就是性价比最高的物品，也不一定能达到最大价值，因为物品不可分割，有可能存在背包没有装满，却不能装下剩下的物品，这样的价值不一定最高。
因此，使用贪心策略解决上述问题不一定能得到最优解。
物体可以分割
但是，如果在物体可以分割的前提下，使用贪心策略每次选择剩余物品中单位价值最高的物品放入背包，得到的价值最大。
问题：
假设现在有 5 个物品，每个物品的重量为（2，5，4，2，3），价值为（6，3，5，4，6），背包的容量为 10，求在不超过背包容量的前提下，把哪些物品放入背包，才能获得最大价值？
代码如下：
W = 10
goods = [{'w': 2, 'v': 6}, {'w': 5, 'v': 3}, {'w': 4, 'v': 5}, {'w': 2, 'v': 4}, {'w': 3, 'v': 6}]# 根据单位价值倒序排序
goods.sort(key=lambda x: x['v'] / x['w'], reverse=True)print(goods)value = 0for item in goods:if item['w'] <= W:value += item['v']W -= item['w']else:value += (item['v']/item['w']) * Wbreakprint(value) # 19.75