对于如下描述的背包问题，请计算最终装入背包的最大价值和以及各个物品装入背包的数量。 背包容量：C＝50千克。3件物品。物品1重20千克，价值100元；物品2重20千克，价值120元；物品3重30千克，价值90元。
第1题：
阅读下列说明，回答问题1至问题2，将解答填入答题纸的对应栏内。
【说明】
0—1背包问题可以描述为：有n个物品，对i=l，2，…，n，第i个物品价值为vi，重量为wi(vi和wi为非负数)，背包容量为w(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即
，且总重量不超过背包容量，即
，其中，xi∈{O，1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。
用回溯法求解此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：当前已获得的部分解。
BKNAP(W，n，w，v，fw，fp，X)
1 cw←cp0
2 (1)
3 fp←l
4 while true
5 while k≤n and cw+w[k]≤w d。
6 (2)
7 cp←cp+v[k]
8 Y[k]←l
9 k←k+1
10 if k>n then
11 if fp<cp then
12 fp←cp
13 fw←cw
14 k←n
15 X←Y
16 else Y (k)←O
17 while BOUND(cp，cw，k，W) ≤fp do
18 while k≠O and Y(k)≠l d0
19 (3)
20 if k=0 then return
2l Y[k]←0
22 cw←cw-w[k]
23 cp←cp-v[k]
24 (4)
第2题：
0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi ，重量为wi（vi，和wi为非负数），背包容量为W（W为非负数），选择其中一些物品装入背包，使装入背包物品的总价值最大，
，且总重量不超过背包容量，即
，其中，xi∈{0,1}，xi=0表示第i个物品不放入背包，xi=1表示第i个物品 放入背包。
【问题1】（8分）
用回溯法求解此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：当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X）
1 cw ← cp ← 0
2 （1）
3 fp ← -1
4 while true
5 while k≤n and cw＋w[k]≤W do
6 （2）
7 cp ← cp＋v[k]
8 Y[k]← 1
9 k ← k+1
10 if k＞n then
11 if fp＜cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 （3）
20 if k＝0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 （4）
本题考查的是用回溯法求解0-1背包问题。回溯法有两类算法框架：非递归形式和递归形式，本题采用非递归形式表示。理解回溯法的基本思想和这两类算法框架是正确解答本题的根本要求·回溯法从第一项物品开始考虑是否应该装入背包中，因此当前考虑的物品编号k从1开始，即k←1。然后逐项往后检查，若能全部放入背包则将该项放入背包，此时背包的重量应该是当前的重量加上当前考虑物品的重量，即cw←cw+w[k]，当然背包中物品的价值也为当前的价值加上当前考虑物品的价值。若己经考虑完了所有的物品，则得到一个解，判断该解是否为当前最优，若为最优，则将该解的信息放入变量fp、fw和X中。若还没有考虑完所有的物品，意味着有些物品不能放入背包，此时先判断若不将当前的物品放入背包中，则其余物品放入背包是否可能得到比当前最优解更优的解，若得不到则回溯；否则继续考虑其余的物品。
【问题1】（共8分，各2分）
（1）k ← 1 或其等价形式
（2）cw ← cw + w[k] 或其等价形式
（3）k ← k – 1 或其等价形式
（4）k ← k + l 或其等价形式
第3题：
关于背包加密算法的描述中，正确的是
A.保证绝对安全
B.物品总重量公开
C.背包问题属于NP问题
D.属于对称加密算法
E.一次背包已不安全
第4题：
第5题：
【问题 1】（8 分）
用回溯法求解此 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：当前已获得的部分解。
第6题：
利用贪心法求解0/1背包问题时，(55)能够确保获得最优解。用动态规划方法求解 0/1背包问题时，将“用前i个物品来装容量是X的背包”的0/1背包问题记为KNAP(1,i,X)，设fi(x)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为 wj和pj(j=1～n)。则依次求解f0(x)、f1(x)、...、fn(X)的过程中使用的递推关系式为(56)。.
A．优先选取重量最小的物品
B．优先选取效益最大的物品
C．优先选取单位重量效益最大的物品
D．没有任何准则
第7题：
考虑一个背包问题，共有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
第8题：
阅读下列函数说明和C代码，填入(n)处字句，并回答相应问题。
[说明]
背包问题就是有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。
背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。
常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到limitweight，这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为图11-4。
仔细阅读程序说明和C程序流程图及源码，回答问题1和问题2。
[流程图11-4]
[程序说明]
struct Thing：物品结构
typedef struct Bag：背包结构类型
input ( )：将物品按序号依次存入数组函数
inbag ( )：物品按物价比入包函数
init ( )：初始化函数
sort ( )：对物品按价格重量比排序函数
outbag ( )：取出包中weiht最大的物品函数
print ( )：最佳方案输出函数
[C程序]
define N 255
struct Thing {
double weight;
double value;
double dens;
}thing[N];
typedef stmct Bag {
Thing thing [N];
double weighttmp;
double sumvalue;
}bag,best;
inbag ( )
{
do{
bag.thing[i]=thing[i]
(1)
(2)
i++;
}while ( (3) )
}
init ( )
{
for (inti=0; i＜N; i++)
{
input (thing[i].weight, thing [i].value)
thing [i].dens=thing[i].value/thing [i].weight;
};
}
main ( )
{
init ( );
sort ( );
inbag ( );
do {
best=bag; //把包中物品放入暂存数组
outbag ( ); //取出包中weight最大的物品
(4)
}while ( (5))
print (best)； //输出temp因为是最佳方案
}
根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。
第9题：
第10题：
