博主自己手撸代码，若有错误，感谢指出  直接上代码

目录

0 贪心算法 

1 代码

2 结果分析

---

0 贪心算法 

贪心算法是一个只关注眼前利益的算法，看起来比较短视，没有长远眼光，但在某些时候会取得比较好的收益。

1 代码

因为python中list自带排序算法，因此博主并没有写排序算法，看起来比较短

m = eval(input('可承载的最大重量：'))
h = eval(input('宝物重量：'))
v = eval(input('宝物价值：'))

# 计算权重, 整合得到一个数组
arr = [(i,v[i]/h[i], h[i], v[i]) for i in range(len(h))]

# 按照list中的权重，从大到小排序
arr.sort(key=lambda x:x[1], reverse=True)  # list.sort() list排序函数

bagVal = 0
bagList = []
for i,w,h,v in arr:
    # 1 如果能放的下宝物，那就把宝物全放进去
    if w <= m:
        m -= h
        bagVal += v
        bagList.append(i)
    
    # 2 如果宝物不能完全放下，考虑放入部分宝物
    else:
        bagVal += m * w
        bagList.append(i)
        break

print('\n排序后：',arr)
print('能运走的最大价值：%.2f'%bagVal,'此时承载的宝物有：',bagList)

"""
毛驴可承载的最大重量：10
宝物重量：2,3,4,7
宝物价值：1,3,5,9

排序后： [(4, 1.2857142857142858, 7, 9), (3, 1.25, 4, 5), (2, 1.0, 3, 3), (1, 0.5, 2, 1)]
能运走的最大价值：12.75 此时承载的宝物有： [4, 3]
"""

2 结果分析

指路博主的文 《【算法】动态规划 背包问题 python》

同一个背包问题，对比两篇博文的结果，可以发现结果不一样。在动态规划中，选择的是4号和2号物品，最大价值为12。

原因在于，动态规划中我们宝物不能切割，因此要选择重量加起来正正好的4号和2号物品。