分支限界法不能解决0/1背包问题

题目

分支限界法不能解决0/1背包问题

相似考题

1.分支限界法主要有队列式(FIFO)分支限界法和优先队列式分支限界法。()此题为判断题(对，错)。

2.分支限界法能解决0／1背包问题的是。()此题为判断题(对，错)。

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

4.解决0／1背包问题只可以使用动态规划和分支限界法。()此题为判断题(对，错)。

更多“分支限界法不能解决0/1背包问题”相关问题

  • 第1题：

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

    A．分支限界法

    B．贪心算法

    C．回溯法

    D．动态规划策略


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

  • 第2题：

    从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（）之外都是最常见的方式。

    • A、队列式分支限界法
    • B、优先队列式分支限界法
    • C、栈式分支限界法
    • D、FIFO分支限界法

    正确答案:C

  • 第3题：

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

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

    正确答案:A

  • 第4题：

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


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

  • 第5题：

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

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

    正确答案:A

  • 第6题：

    分支限界法主要有（）分支限界法和（）分支限界法。


    正确答案:队列式（FIFO）；优先队列式

  • 第7题：

    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。


    正确答案:子集树

  • 第8题：

    举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。


    正确答案: 举例如：
    p{7，4，4}，w={3，2，2}，c=4时，
    由于7/3最大，
    若按题目要求的方法，只能取第一个，收益是7。
    而此实例的最大的收益应该是8，取第2，3 个。

  • 第9题：

    问答题
    举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

    正确答案： 举例如：
    p{7，4，4}，w={3，2，2}，c=4时，
    由于7/3最大，
    若按题目要求的方法，只能取第一个，收益是7。
    而此实例的最大的收益应该是8，取第2，3 个。
    解析： 暂无解析

  • 第10题：

    单选题
    常见的两种分支限界法为（）
    A

    广度优先分支限界法与深度优先分支限界法

    B

    队列式（FIFO）分支限界法与堆栈式分支限界法

    C

    排列树法与子集树法

    D

    队列式（FIFO）分支限界法与优先队列式分支限界法


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

  • 第11题：

    填空题
    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

    正确答案： 子集树
    解析： 暂无解析

  • 第12题：

    单选题
    从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（）之外都是最常见的方式。
    A

    队列式分支限界法

    B

    优先队列式分支限界法

    C

    栈式分支限界法

    D

    FIFO分支限界法


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

  • 第13题：

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

    （65）

    A. 分支限界法

    B. 贪心算法

    C. 回溯法

    D. 动态规划策略


    正确答案：B

  • 第14题：

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

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

    正确答案:D

  • 第15题：

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

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

    正确答案:C

  • 第16题：

    以下不可以使用分治法求解的是（）。

    • A、棋盘覆盖问题
    • B、选择问题
    • C、归并排序
    • D、0/1背包问题

    正确答案:D

  • 第17题：

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

    • A、回溯法
    • B、分支限界法
    • C、回溯法和分支限界法
    • D、回溯法求解子集树问题

    正确答案:B

  • 第18题：

    常见的两种分支限界法为（）

    • A、广度优先分支限界法与深度优先分支限界法
    • B、队列式（FIFO）分支限界法与堆栈式分支限界法
    • C、排列树法与子集树法
    • D、队列式（FIFO）分支限界法与优先队列式分支限界法

    正确答案:D

  • 第19题：

    描述0-1背包问题。


    正确答案:已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

  • 第20题：

    单选题
    以下不可以使用分治法求解的是（）。
    A

    棋盘覆盖问题

    B

    选择问题

    C

    归并排序

    D

    0/1背包问题


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

  • 第21题：

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

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

    B

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

    C

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

    D

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


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

  • 第22题：

    填空题
    分支限界法主要有（）分支限界法和（）分支限界法。

    正确答案： 队列式（FIFO）,优先队列式
    解析： 暂无解析

  • 第23题：

    问答题
    描述0-1背包问题。

    正确答案： 已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。
    解析： 暂无解析

  • 第24题：

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

    贪心法

    B

    动态规划

    C

    回溯法

    D

    分支限界法


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

相关内容