未分类题

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