简答题

请叙述动态规划算法与贪心算法的异同。

正确答案

共同点:
都需要最优子结构性质,
都用来求有优化问题。
不同点:
动态规划:每一步作一个选择—依赖于子问题的解。
贪心方法:每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件:子问题的重叠性质。
可用贪心方法的条件:最优子结构性质;贪心选择性质。
动态规划:自底向上求解;
贪心方法:自顶向下求解。
可用贪心法时,动态规划方法可能不适用;
可用动态规划方法时,贪心法可能不适用。

答案解析

相似试题
  • 贪心算法与动态规划算法的主要区别是()。

    单选题查看答案

  • ()是贪心算法与动态规划算法的共同点。

    单选题查看答案

  • ()是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。

    填空题查看答案

  • 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的()。

    单选题查看答案

  • 问题的()是该问题可用动态规划算法或贪心算法求解的关键特征。

    填空题查看答案

  • 算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么?

    简答题查看答案

  • 对下图所示的连通网络G,用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中,依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想,并简要分析算法的时间复杂度。

    简答题查看答案

  • 贪心算法算法的基本要素是()、()。

    填空题查看答案

  • 简述动态规划算法的基本步骤。

    简答题查看答案