【说明】
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为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；
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("%d\t"，w[x.n+1])；
return k；
