关于背包问题，正确的是（)

A、使用约束函数剪去不合理的左子树（装该物品）。

B、使用限界函数剪去得不到更优解的左子树（装该物品）。

C、使用约束函数剪去不合理的右子树（不装该物品）。

D、使用限界函数剪去得不到更优解的右子树（不装该物品）。

A.保证绝对安全

B.物品总重量公开

C.背包问题属于NP问题

D.属于对称加密算法

E.一次背包已不安全

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

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

用贪婪算法解决背包问题，贪婪准则为：每次都选择值（价值密度）最大的物品装包。假设n=3；=40，=40；=10，=20；=15，=45；C=45。下列说法不正确的是 （ ）

A、利用价值密度最大的贪婪准则时，选物品1，这种方案的总价值为40

B、最优解选物品为2和3，总价值为65

C、就本题而言，使用贪婪准则，能保证得到最优解

D、利用价值密度最大的贪婪准则时，选物品2和3，总价值为65

B.离散对数

C.NPC

D.P

用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。

回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。

下面给出 0-1背包问题的回溯算法伪代码。

函数参数说明如下:

W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。

变量说明如下：

cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。