0-1背包问题 n=5，背包容量c=8，物品的重量为W=[2,2,7,5,4]，其价值为V=[3,6,4,5,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

阅读下列程序说明和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；

}

A、101

B、110

C、115

D、120

●试题四

阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

【程序4．1说明】

"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为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(″N0!＼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=l；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；

}

已知序列x(n)=3§(n)+5§(n-2)+4§(n-4).则可求出8点DFT为X(k)

(1)若y(n)(0≤n≤7)的8点DFT为Y(k)=W8^3kX(k),0≤k≤7,求y(n)

(2)若w(n)(0≤u≤7)的8点DFT为W(k)=R_e[X(k)],0≤k≤7,水w(n)

(3)若u(n)(0≤n≤3)的4点DFT为U(k)=X(2k),0≤n≤3,求u(n)。

A、4/3,1

B、8/5,1

C、4/3,2

D、8/5,2

4，5，3，6，8，1，( )，11

A．-2

B．0

C．2

D．4

腻子中掺入催干剂量一般为腻子总重量的()%。

A、1~2

B、3~4

C、5~6

D、7~8