判断题
适中
#24881
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。()
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。()
答案与解析
正确答案:错
解析
分析问题是否具备最优子结构性质,即原问题的最优解是否包含其子问题的最优解。考察贪心算法适用条件,需验证该问题是否同时满足贪心选择性质和最优子结构。贪心选择性质要求局部最优选择能导向全局最优解,可通过构造法或交换论证判断每次贪心决策能否保持最优性。若仅满足最优子结构而不满足贪心选择性质,则无法保证贪心算法得到最优解。动态规划适用于具有最优子结构的问题,而贪心算法是更特殊的情形,需额外满足贪心选择性质。