算法设计与分析
关于0－1背包问题以下描述正确的是（）A、可以使用贪心算法找到最优解B、能找到多项式时间的有效算法C、使用教材介绍的动态规划方法可求解任意0－1背包问题D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
题目
关于0－1背包问题以下描述正确的是（）
- A、可以使用贪心算法找到最优解
- B、能找到多项式时间的有效算法
- C、使用教材介绍的动态规划方法可求解任意0－1背包问题
- D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
相似问题和答案
第1题：
如果不考虑排序的时间，背包问题贪心算法的时间就是
循环语句：
for i=1 to n do执行的时间，循环体语句可以用常数c表示，
算法的时间复杂性为：T(n)=cn。
第2题：
● （65） 不能保证求得0-1 背包问题的最优解。
（65）
A. 分支限界法
B. 贪心算法
C. 回溯法
D. 动态规划策略
第3题：
关于背包加密算法的描述中，正确的是
A.保证绝对安全
B.物品总重量公开
C.背包问题属于NP问题
D.属于对称加密算法
E.一次背包已不安全
背包加密算法是一种公钥加密算法，该算法中背包的物品总重量是公开的，所有可能的物品也是公开的，但是背包中的物品却是保密的，它是一个NP难度问题。目前大多数一次背包体制均被破译了，一次背包已不安全了。根据解析选项BCE符合题意，故选择BCE项。
第4题：
对于0－1背包问题和背包问题的解法，下面（）答案解释正确。
- A、0－1背包问题和背包问题都可用贪心算法求解
- B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
- C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
- D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解
正确答案:C
第5题：
0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。
正确答案: O(n*2n)；O(min{nc,2n})
第6题：
考虑一个背包问题，共有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.11
B.14
C.15
D.16.67
第7题：
B.矩阵连乘
C.最长公共子序列
D.邻分（分数）背包
第8题：
不能保证求得0-1背包问题的最优解。
A．分支限界法
B．贪心算法
C．回溯法
D．动态规划策略
解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。
第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背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 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。
第10题：
用贪心算法设计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]；
}