判断题
适中
#24800
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。
答案与解析
正确答案:错
解析
分析问题是否具备最优子结构性质,即全局最优解包含子问题的最优解。确认贪心选择性质是否存在,即每一步的局部最优选择能否导向全局最优解。验证贪心策略与最优子结构之间的对应关系,检查是否存在反例表明贪心选择无法保持最优性。考察动态规划与贪心算法在结构上的差异,明确两者对最优子结构的不同依赖方式。