2. 从业资格
  3. 采用贪心算法保证能求得最优解的问题是（　　）。A.0-1背包 B.矩阵链乘

采用贪心算法保证能求得最优解的问题是（　　）。A.0-1背包 B.矩阵链乘

免费题库2022-08-02  65
问题 采用贪心算法保证能求得最优解的问题是（　　）。A.0-1背包B.矩阵链乘C.最长公共子序列D.部分（分数）背包
选项 A.0-1背包
B.矩阵链乘
C.最长公共子序列
D.部分（分数）背包
答案 D
解析 贪心法在一般情况下一定能够得到满意解，不一定能够得到最优解。
贪心法能够获得最优解的前提是：（1）问题具有最优子结构，即规模为n的问题的最优解与规模为n-1的问题的解相关；（2）问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择得到。
部分背包问题具有以上性质，故可以通过贪心算法得到最优解。
转载请注明原文地址:https://tihaiku.com/congyezige/2409514.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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