如果一个最值问题可以用动态规划在多项式时间内求解,那么也一定存在一种贪心策略,可以在多项式时间 内求得最优解。
A:正确
B:错误
正确答案:错误
答案解析
动态规划适用于具有最优子结构和重叠子问题的问题,通过自底向上求解所有子问题保证全局最优。贪心算法基于贪心选择性质,在每一步选择局部最优,期望达到全局最优,其正确性依赖于问题是否满足贪心选择性和最优子结构。两个算法的适用条件不同:动态规划能解决的问题不一定满足贪心选择性质,因此无法保证存在贪心策略得到最优解。判断时需分析两类算法对问题结构性质的要求差异,不能由动态规划可解推出贪心策略必然存在。
试卷来源:202603 CCF-GESP编程能力等级认证C++七级真题