贪婪算法

DNA图谱 / 问答 / 标签

用动态规划算法和贪婪算法求解01背包问题的区别

首先这两个算法是用来分别解决不同类型的背包问题的,不存在哪个更优的问题。 当一件背包物品可以分割的时候,使用贪心算法,按物品的单位体积的价值排序,从大到小取即可。 当一件背包物品不可分割的时候,(因为不可分割,所以就算按物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的,应使用动态规划。