阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 “背包问题”的基本描述是:有

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

【说明】

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

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

【程序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)){/*考虑物品n被选择的情况*/

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

return 1;

}

return (2);/*考虑不选择物品n的情况*/

}

main()

{

if(knap(S,N))printf("OK!\n");

else printf("N0!\n");

}

【程序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("0K!\n");

else printf("N0!\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=1; 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;

}

}/*while*/

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*/

}/*while*/

}/*if*/

/*while*/

if(k){&nbs