阅读下列程序说明和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! ")；
else printf("NO! ")；
}
【程序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! ")；
else printf("NO! ")；}
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 "，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 解析：试题提供了两种解决问题的方法，程序5.1是用递归的方法来解决背包问题，程序5.2使用非递归的方法来解决背包问题。每次选择一个物品放入背包，那么剩余的物品和背包剩余的重量，又构成一个“背包问题”。程序从数组下标最大的物品开始考查，因此(1)处应该填“knap(s-w[n]，n-1)”，即将数组中第N个物品放入背包，如果它能够放入到背包中，则该物品是构成解的元素之一；否则，将该物品从背包中取出，该物品不构成解的元素，在以后的考查中，它可以被排除，因此(2)处应该填“knap(s，n-1)”。在改程序中用栈来保存已经考查过的物品，结构KNAPTP表示经过考查的物品，s表示考查过该物品后背包所能够盛放的物品的重量；n表示该物品在数组W中的下标；job表示物品当前的状态：当job等于1，表示物品n可以放入背包； job等于2表示物品n不能被放入到背包，那么在以后的选取中将不再考虑该物品。初始时job等于0，表示背包中没有任何放入任何物品。 K为有解的标志。Rep为一个标志变量，rep等于0，表示结束当前的动作；rep等于1表示继续进行当前的动作。当栈顶物品不能放入背包时，将rep设置为0，表示下一步不从数组w中取物品。其初值为1。开始时，将数组中下标最大的物品放入栈中，然后开始考查该物品。该物品满足放入背包的条件，第(4)(5)空将完成将物品放入背包的操作，因此(4)空填“x.s-w[x.n--]”，修改背包的可容纳物品的重量； (5)处填"stack[++top]"，将下一个要考查的物品放入栈中。若该物品不满足放入背包的条件，则将该物品从背包中取出，因此将rep置为 0，结束循环while(! k&&rep)。将物品从背包中取出，即释放该物品在背包中所占的重量，并标记为不能放入到背包(job=2)，再将其放入到栈中；然后继续考查数组w中的下一个物品，因此需要结束循环while (top＞=1 &&rep)，将rep置为0，所以第(6)处应该填“rep=0”。在第三处要求给出循环结束的条件，即可以继续选取物品的条件，在此处填“top＞=1&&!k”。