[说明]
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1、w2、…、wn，希望从N件物品中选出若干件物品，并使所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
[函数]
#include ＜stdio.h＞
#define N 7
#define S 15
typedef struct
int s;
int n;
int job;
KNAPTP;
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 (1)
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= (2) ;
x. job=1;
(3) =x;


if(!k)
rep=1;
while(top＞=1＆＆rep)
x=stack [top--1];
if (x,job=1)
x.s+=w[x.n+1];
(4) ;
stack [++top] =x;
(5) ;



if(k)
while (top＞=1)
x=stack [top--] ;
if (x.job==1)
printf ("M\t",w[x.n+1]) ;



return k;

无菌检验