Question

采用贪心算法保证能求得最优解的问题是（　　）。

A.0-1背包
B.矩阵链乘
C.最长公共子序列
D.部分（分数）背包

Answer 1

【答案】：D
贪心法在一般情况下一定能够得到满意解，不一定能够得到最优解。
贪心法能够获得最优解的前提是：（1）问题具有最优子结构，即规模为n的问题的最优解与规模为n-1的问题的解相关；（2）问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择得到。
部分背包问题具有以上性质，故可以通过贪心算法得到最优解。