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