2. 从业资格
  3. （　　）不能保证求得0-1背包问题的最优解。A.分支限界法 B.贪心算法 C

（　　）不能保证求得0-1背包问题的最优解。A.分支限界法 B.贪心算法 C

练习题库2022-08-02  68
问题 （　　）不能保证求得0-1背包问题的最优解。A.分支限界法B.贪心算法C.回溯法D.动态规划策略
选项 A.分支限界法
B.贪心算法
C.回溯法
D.动态规划策略
答案 B
解析 分支限界法一般以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间，那么肯定能找出最优解。
贪心算法的思想是：总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。所以用该算法并不能保证求得0-1背包问题的最优解。
回溯法的思想是：按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。它其实是遍历了整个解空间，所以肯定能找到最优解。
动态规划法的思想是：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。它能求得0-1背包问题的最优解。
转载请注明原文地址:https://tihaiku.com/congyezige/2410131.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)