动态规划与贪婪算法的区别

动态编程 贪婪法
1.使用动态规划来获得最佳解决方案。 1.还使用贪婪方法来获得最佳解决方案。
2.在动态编程中, 我们在每个步骤中进行选择, 但是选择可能取决于子问题的解决方案。 2.在贪婪算法中, 我们使任何选择当前都看起来最合适, 然后解决选择之后产生的子问题。
3.与贪婪的方法相比效率较低 3.比贪婪的方法更有效率
4.示例:0/1背包 4.示例:小背包
5.保证动态规划将使用最优原理生成最优解决方案。 5.在贪婪方法中, 无法保证获得最佳解决方案。

    推荐阅读