问答题

[说明]
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w₁，W₂，…，W_n，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于s。
如下程序均能求得“背包问题”的一组解，其中，程序1—8是“背包问题”的递归解法，而程序1-9是“背包问题”的非递归解法。
[程序1—8]
#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))) /*考虑物品n被选择的情况*/
printf("4d"w[n])；return 1；
return(2)； /*考虑不选择物品n的情况*/

main()
if(knap(S，N))printf("OK!＼n")；
else printf("N0!\n")；

[程序1-9]
#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=1；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=O；
elsex.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("M\t, w[x.n+1])；



return k；