itgle.com

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

题目

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

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

1.关于背包加密算法的描述中，正确的是A.保证绝对安全B.物品总重量公开C.背包问题属于NP问题D.属于对称加密算法E.一次背包已不安全

2.背包问题贪心算法的时间复杂性。

3.考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为其中c(i，j)表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c(n,W)。 采用自底向上的动态规划方法求解，得到最大装包价值为(62)，算法的时间复杂度为(63)。 若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为(64)，算法的时间复杂度为(65)。A.11B.14C.15D.16.67

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

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

  • 第1题：

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

    （65）

    A. 分支限界法

    B. 贪心算法

    C. 回溯法

    D. 动态规划策略


    正确答案：B

  • 第2题：

    0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。


    正确答案: O(n*2n)；O(min{nc,2n})

  • 第3题：

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

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

    正确答案:C

  • 第4题：

    一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？


    正确答案:按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。

  • 第5题：

    有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？


    正确答案: 因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。

  • 第6题：

    关于背包加密算法的描述中，正确的是（）

    • A、保证绝对安全
    • B、物品总重量公开
    • C、背包问题属于NP问题
    • D、属于对称加密算法
    • E、一次背包已不安全

    正确答案:B,C,E

  • 第7题：

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


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

  • 第8题：

    问答题
    用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。

    正确答案： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
    具体算法可描述如下：
    void Knapsack（int n，float M，float v[]，float w[]，float x[]）
    {Sort（n，v，w）；
    int i；
    for（i=1；i<=n；i++） x[i]=0；
    float c=M；
    for（i=1；i<=n；i++）
    {if（w[i]>c） break；
    x[i]=1；
    c-=w[i]；
    }
    if（i<=n）x[i]=c/w[i]；
    }
    解析： 暂无解析

  • 第9题：

    问答题
    有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？

    正确答案： 因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。
    解析： 暂无解析

  • 第10题：

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

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

  • 第11题：

    填空题
    0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。

    正确答案： O(n*2n),O(min{nc,2n})
    解析： 暂无解析

  • 第12题：

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

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

    B

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

    C

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

    D

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


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

  • 第13题：

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

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

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

  • 第14题：

    有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）


    正确答案: 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
    1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
    2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
    3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
    4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
    由于8>5，所以不能再放进背包。
    结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。

  • 第15题：

    用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。


    正确答案: 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
    具体算法可描述如下：
    void Knapsack（int n，float M，float v[]，float w[]，float x[]）
    {Sort（n，v，w）；
    int i；
    for（i=1；i<=n；i++） x[i]=0；
    float c=M；
    for（i=1；i<=n；i++）
    {if（w[i]>c） break；
    x[i]=1；
    c-=w[i]；
    }
    if（i<=n）x[i]=c/w[i]；
    }

  • 第16题：

    0-1背包问题的回溯算法所需的计算时间为（）

    • A、O（n2n）
    • B、O（nlogn）
    • C、O（2n）
    • D、O（n）

    正确答案:A

  • 第17题：

    在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）


    正确答案: 对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。贪心策略如下：
    首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。
    这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。

  • 第18题：

    描述0-1背包问题。


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

  • 第19题：

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

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

    B

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

    C

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

    D

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


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

  • 第20题：

    问答题
    有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）

    正确答案： 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
    1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
    2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
    3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
    4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
    由于8>5，所以不能再放进背包。
    结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。
    解析： 暂无解析

  • 第21题：

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

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

  • 第22题：

    问答题
    一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？

    正确答案： 按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。
    解析： 暂无解析

  • 第23题：

    问答题
    在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）

    正确答案： 对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。贪心策略如下：
    首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。
    这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。
    解析： 暂无解析

相关内容