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

第1题：

第2题：

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

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

正确答案:D

第3题：

下列哪一种算法是随机化算法（）

• A、贪心算法
• B、回溯法
• C、动态规划算法
• D、舍伍德算法

正确答案:D

第4题：

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

正确答案:O(h(n))

第5题：

背包问题的贪心算法所需的计算时间为（）

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

正确答案:B

第6题：

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

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

正确答案:A

第7题：

描述0-1背包问题。

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

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

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

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

正确答案:C

第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题：

矩阵连乘问题的算法可由（）设计实现。

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

正确答案:B

第17题：

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

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

正确答案:A

第18题：

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

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

第19题：

第20题：

第21题：

第22题：

第23题：