实验4 “0-1”背包问题(4)

七、实验分析 解决0/1背包问题的方法有多种，最常用的有贪心法和动态规划法。其中贪心法无法得到问题的最优解，而动态规划法都可以得到最优解。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪心算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心算法中，每采用一次贪心准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库实验4 “0-1”背包问题(4)在线全文阅读。