Python使用贪婪法及其改进算法求解0-1背包问题
- 2019 年 11 月 22 日
- 笔记
贪婪法基本思想：
首先按物品单位价值（物品价值/物品重量或体积）降序排序，然后逐个尝试是否能放进背包而不超过背包容量，直到遇到无法放入背包的物品就结束。
改进思路：
遇到放不进背包的物品就跳过去，看看排在后面的单位价值小的物品还有没有能放进背包的。
参考代码：
运行结果：
QNews
贪婪法基本思想：
首先按物品单位价值（物品价值/物品重量或体积）降序排序，然后逐个尝试是否能放进背包而不超过背包容量，直到遇到无法放入背包的物品就结束。
改进思路：
遇到放不进背包的物品就跳过去，看看排在后面的单位价值小的物品还有没有能放进背包的。
参考代码：
运行结果：