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

免费题库2022-08-02  44

问题 采用贪心算法保证能求得最优解的问题是(  )。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)