●试题四

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

}