阅读下列程序说明和C＋＋代码,将应填入(n)处。 【说明】 “背包问题”的基本描述是:有一个背包,能盛放的

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

}

正确答案：

(1)knap(s-w[n]n-1)(2)knap(sn-1)(3)top＞=1 && ! k 或 top＞0 && k==0(4)x.s-w[x.n--](5)stack[++top](6)rep=0(1)knap(s-w[n]，n-1)(2)knap(s，n-1)(3)top＞=1 && ! k 或 top＞0 && k==0(4)x.s-w[x.n--](5)stack[++top](6)rep=0 解析：试题提供了两种解决问题的方法，