itgle.com

● （65） 不能保证求得0-1 背包问题的最优解。（65）A. 分支限界法B. 贪心算法C. 回溯法D. 动态规划策略

题目

● （65） 不能保证求得0-1 背包问题的最优解。

（65）

A. 分支限界法

B. 贪心算法

C. 回溯法

D. 动态规划策略

相似考题

1.实现最长公共子序列利用的算法是()A.分治策略B.动态规划法C.贪心法D.回溯法

2.实现最大子段和利用的算法是()A.分治策略B.动态规划法C.贪心法D.回溯法

3.合并排序算法是利用()A.分治策略B.动态规划法C.贪心法D.回溯法

4.矩阵连乘问题的算法可由什么设计实现()A.分支界限算法B.动态规划算法C.贪心算法D.回溯算法

更多“● （65） 不能保证求得0-1 背包问题的最优解。（65）A. 分支限界法B. 贪心算法C. 回溯法D. 动态规划策略”相关问题

  • 第1题：

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

    A.重叠子问题

    B.构造最优解

    C.贪心选择性质

    D.最优子结构性质


    参考答案：D

  • 第2题：

    解决0／1背包问题可以使用动态规划、回溯法和分支限界法,其中不需要排序的是动态规划,需要排序的是回溯法,分支限界法。()

    此题为判断题(对，错)。


    正确答案:√

  • 第3题：

    算法策略与递归技术的联系最弱。

    A．动态规划

    B．贪心

    C．回溯

    D．分治


    正确答案：B
    解析：对于具有最优子结构和重叠子问题的问题，可以用动态规划求解问题，求解过程中通常需要建立最优子结构的递归关系。分治算法的基本思想是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。回溯算法也称为试探算法，该算法首先放弃关于问题规模大小的限制，并将问题的候选解按某种次序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解，若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。用回溯算法找解的算法常常被编写成递归函数。贪心算法是一种不追求最优解，而是希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费大量的时间。贪心法不要回溯。因此贪心算法策略与递归技术的联系最弱。

  • 第4题：

    （接上一题）若定义问题的解空间，以深度优先的方式搜索解空间，则采用（65）算法设计策略。

    A.动态规划

    B.贪心

    C.回溯

    D.分支限界


    正确答案：C
    同上一题解析

  • 第5题：

    在求解某问题时，经过分析发现该问题具有最优子结构性质，若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ ）算法设计策略。

    A.动态规划
    B.贪心
    C.回溯
    D.分支限界

    答案：C
    解析：
    分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
    动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
    贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。
    回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
    题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

  • 第6题：

    下列算法中通常以自底向下的方式求解最优解的是（）

    • A、分治法
    • B、动态规划法
    • C、贪心法
    • D、回溯法

    正确答案:B

  • 第7题：

    在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）

    • A、回溯法
    • B、分支限界法
    • C、回溯法和分支限界法
    • D、动态规划

    正确答案:A

  • 第8题：

    解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（），（）。


    正确答案:动态规划；回溯法；分支限界法

  • 第9题：

    采用广度优先策略搜索的算法是（）。

    • A、分支界限法
    • B、动态规划法
    • C、贪心法
    • D、回溯法

    正确答案:A

  • 第10题：

    单选题
    下列算法中通常以自底向下的方式求解最优解的是（）
    A

    分治法

    B

    动态规划法

    C

    贪心法

    D

    回溯法


    正确答案： D
    解析： 暂无解析

  • 第11题：

    单选题
    对于0－1背包问题和背包问题的解法，下面（）答案解释正确。
    A

    0－1背包问题和背包问题都可用贪心算法求解

    B

    0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解

    C

    0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解

    D

    因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解


    正确答案： A
    解析： 暂无解析

  • 第12题：

    填空题
    解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（），（）。

    正确答案： 动态规划,回溯法,分支限界法
    解析： 暂无解析

  • 第13题：

    二分搜索算法是利用什么实现的算法()

    A.分治策略

    B.动态规划法

    C.贪心法

    D.回溯法


    参考答案：A

  • 第14题：

    不能保证求得0-1背包问题的最优解。

    A．分支限界法

    B．贪心算法

    C．回溯法

    D．动态规划策略


    正确答案：B
    解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。

  • 第15题：

    以下的算法设计方法中，( )以获取问题最优解为目标。

    A．回溯方法

    B．分治法

    C．动态规划

    D．递推


    正确答案：C
    解析：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是；适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值(最大值或最小值)的那个解。

  • 第16题：

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

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

    答案：D
    解析：
    动态规划算法适合解决0-1背包问题，贪心法适合解决部分背包（邻分（分数）背包）问题。

  • 第17题：

    下列算法中通常以自底向上的方式求解最优解的是（）。

    • A、备忘录法
    • B、动态规划法
    • C、贪心法
    • D、回溯法

    正确答案:B

  • 第18题：

    关于0－1背包问题以下描述正确的是（）

    • A、可以使用贪心算法找到最优解
    • B、能找到多项式时间的有效算法
    • C、使用教材介绍的动态规划方法可求解任意0－1背包问题
    • D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题

    正确答案:D

  • 第19题：

    对于0－1背包问题和背包问题的解法，下面（）答案解释正确。

    • A、0－1背包问题和背包问题都可用贪心算法求解
    • B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
    • C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
    • D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解

    正确答案:C

  • 第20题：

    下列算法中不能解决0/1背包问题的是（）

    • A、贪心法
    • B、动态规划
    • C、回溯法
    • D、分支限界法

    正确答案:A

  • 第21题：

    单选题
    采用广度优先策略搜索的算法是（）。
    A

    分支界限法

    B

    动态规划法

    C

    贪心法

    D

    回溯法


    正确答案： C
    解析： 暂无解析

  • 第22题：

    单选题
    关于0－1背包问题以下描述正确的是（）
    A

    可以使用贪心算法找到最优解

    B

    能找到多项式时间的有效算法

    C

    使用教材介绍的动态规划方法可求解任意0－1背包问题

    D

    对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题


    正确答案： B
    解析： 暂无解析

  • 第23题：

    单选题
    下列算法中不能解决0/1背包问题的是（）
    A

    贪心法

    B

    动态规划

    C

    回溯法

    D

    分支限界法


    正确答案： A
    解析： 暂无解析

相关内容