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

A．装载问题是一个特殊的背包问题

B．装载问题是一个特殊的0-1背包问题

C．装载问题可以用回溯法求解

D．装载问题可以用动态规划法求解

阅读下列说明，回答问题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)

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）

阅读下列程序说明和C++代码，将应填入(n)处。

【说明】

“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1；w2，……，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。

如下程序均能求得“背包问题”的一组解，其中程序4.1是“背包问题”的递归解法，而程序4.2是“背包问题”的非递归解法。

【程序4.1】

include＜stdio.h＞

define N 7

define S 15

int w[N+1]={0，1，4，3，4，5，2，7}；

int knap(int s，int n)

{ if(s==0)return 1；

if(s＜0||(s＞0& &n＜1))return 0；

if((1)))|

printf("%4d"，w[n])；return 1；

} return (2)；

}

main(){

if(knap(S，N))printf("OK!\n")；

else printf("NO!\n")；

}

【程序4.2】

include＜stdio.h＞

define N 7

define S 15

typedef struct{

int s；

int n：

int job；

} KNAPTP；

int w[N+1]={0，1，4，3，4，5，2，7}；

int knap(int s，int n)；

main(){

if(knap(S，N))printf("OK!\n")；

else printf("NO!\n")；}

int knap(int s，int n)

{ KNAPTP stack[100]，x；

int top，k，rep；

x.s=s；x.n=n；

x.job=0；

top=|；Stack[top]=x；

k=0；

while((3)){

x=Stack[top]；

rep=1；

while(!k && rep){

if(x.s==0)k=1；/*已求得一组解*/

else if(x.s＜0||x.n ＜=0)rep＝0；

else{x.s＝(4)；x.job＝1；

(5)=x；

}

}

if(!k){

rep=1；

while(top＞＝1&&rep){

x=stack[top--]；

if(x.job==1){

x.s+=W[x.n+1]；

x.job=2；

Stack[++top]=x；

(6)；

}

}

}

}

if(k){/*输出一组解*/

while(top＞=1){

x＝staCk[top--]；

if(x.job＝＝1)

printf("%d\t"，w[x.n+1])；

}

}

return k；

}

问题描述:设计一个用回溯法搜索子集空间树的函数,参数包括结点可行性判定函数和上界函数等必要的函数,并将此的数用于解0-1背包问题.

0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是w_i,其价值为v_i背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大?

在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.

0-1背包问题形式化描述如下:给定,要求n元0-1向量,使得而且达到最大.

算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.

结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt

阅读以下程序说明和C程序，将程序段中(1)～(7)空缺处的语句填写完整。

【说明】

【C程序1】用回溯算法来产生由0或1组成的2m个二进位串，使该串满足以下要求。

视串为首尾相连的环，则由m位二进制数字组成的2m个子序列，每个可能的子序列都互不相同。例如，如果m=3，在串11101000首尾相连构成的环中，由3位二进制数字组成的每个可能的子序列都在环中恰好出现一次，它们依次是111，110，101，010，100，000，001，011，如图2-14所示。

【C程序2】是求“背包问题”的一组解的递归算法程序。“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为W1，W2，…，Wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。

【C程序1】

define N 1024

define M 10

int b [N+M-1]

int equal(int k, int j int m) {

int i;

for(i=0; i＜m; i++

if ( b[ k + i] (1) )

return 0;

return 1; }

int exchange (int k, int m, int v){

while ( b[ k + m - 1 ) == v ) {

b[ kncm--i]=! v (2);

}

(3)=v;

return k;

}

init ( iht v) {

int k

for( k = 0;K = N + M - 1;k++)

b[k] = v;

}

main ( ) {

int m, v, k, n, j;

printf ('Enter m (l＜m＜10) , v v=0, v=1)\ n") ;

scanf (" %d%d , &m, &v);

n = 0x01 ＜＜ m;

init (!v);

k=0;

while((4)＜ n)

for (j=0;j＜k;j++)

if (equal (k, j, m)) {

k=exchange (k, m, v)

j=(5);

}

for (k= 0 ;k＜n ;k++ )

print{ (" %d\ n" , b[k]) ;

}

}

【C程序2】

include＜stdio. h＞

define N 7

define S 15

int w[N+1] = {0, 1, 4, 3, 4, 5, 2, 7};

int knap (int S, int n){

if (S == 0)

return 1;

if (s＜0 || (s＞0 && n＜1))

return 0;

if ((6))) {

printf( "4d", w[n]);

return 1;

}

return (7)

}

main ( ) {

if (knap (S, N)

printf("OK:\n");

else

printf("NO!\n")

}

考虑下面的整数线性规划问题：其中：是非负整数，且下面（ ）是正确求解过程

A、首先给出该问题的子问题描述：且的最优值为m(j) ，也就是m(j)表示在背包容量是j的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(j)的递归关系式如下：

B、首先给出该问题的子问题描述：且的最优值为m(i,j) ，也就是m(i,j)表示在背包容量是j，可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(i,j)的递归关系式如下：其中初始值，m(0,j)=m(i,0)=0, m(i,j)=

C、首先给出该问题的子问题描述：且的最优值为m(i,j) ，也就是m(i,j)表示在背包容量是j，可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(i,j)的递归关系式如下： m(i,j)=其中初始值，m(0,j)=m(i,0)=0, m(i,j)=

D、可以用贪心算法求解。按照ai递增排序，依次选择第i个物体，只要选择的物体的总值小于b即可

考虑下面的整数线性规划问题：其中：是非负整数，且下面（ ）是正确求解过程

A、首先给出该问题的子问题描述：且的最优值为m(j) ，也就是m(j)表示在背包容量是j的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(j)的递归关系式如下：

B、首先给出该问题的子问题描述：且的最优值为m(i,j) ，也就是m(i,j)表示在背包容量是j，可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(i,j)的递归关系式如下：其中初始值，m(0,j)=m(i,0)=0, m(i,j)=

C、首先给出该问题的子问题描述：且的最优值为m(i,j) ，也就是m(i,j)表示在背包容量是j，可以选择物品1,2,...,i的时候背包问题的最优值。 由背包问题的最优子结构性质，可以建立计算m(i,j)的递归关系式如下： m(i,j)=其中初始值，m(0,j)=m(i,0)=0, m(i,j)=

D、可以用贪心算法求解。按照ai递增排序，依次选择第i个物体，只要选择的物体的总值小于b即可

设有n项任务，加工时间分别表示为正整数。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。 假设问题的解是，其中. 如果，那么第i项任务放到第一台机器上加工；如果，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，从问题本质看，任务的加工时间相当于0-1背包问题中的下述输入参数：

A、既是物品i的价值，也是它的重量

B、仅代表物品i的价值

C、仅代表物品i的重量

D、物品i单位重量的价值