设有一个背包可以放入的物品重量为s 现有n件物品 重量分别为w1 w2 … wn。请设计从这n件物品中选择若干件放入

(1)思路
   先用递归思想分析此问题。
   背包问题如果有解，其选择只有两种可能：
   一种是选择的一组物品中不包含wn，这样原问题的解就是参数为s；n-1；w1，w2，…，wn-1的背包问题的解；另一种是选择中包含wn，这样原问题的解就是参数为s-wn；n-1；w1，w2，…，wn-1的背包问题的解。重复上面的递归操作，经有限次后即可得到背包问题的解。
   当s=0时，背包问题有解。
   当s＜0或s＞0但n＜1时，背包问题无解。
   背包问题可以有递归和非递归两种解决方式。
   用knap(s，n)表示背包问题的解，这个函数返回的值为1表示此问题有解，返回值为0表示无解。
   上述递归定义的函数knap(s，n)是有递归出口的。
   (2)递归算法
   按照背包问题的递归定义，可以写出如下的递归算法：
   int knap(int s,int n)
   {if(s==0)return(1);
   else if((s＜0)((s＞0)&&(n＜1)))return(0);
   else if(knap(s-w[n-1],n-1)==1){
       printf("result:n=%d,w[%d]=%d  ",n,n-1,win-1]);
               return(1);
           }
       else return(knap(s,n-1));
   }
   (3)递归算法向非递归算法的转换
   栈的结点应包含字段s和n以及该结点所表示的背包问题的解的情况，用k表示(有解则k=TRUE；无解，k=FALSE)。
   由于knap算法中有两处要递归调用knap算法，返回地址一共有3种情况：
   ·计算knap(s，n)完毕，返回到调用本函数的其他函数。
   ·计算knap(s-w[n-1]，n-1)完毕，返回到本调用函数中继续计算。
   ·计算kalap(s，n-1)完毕，返回到本调用函数继续计算。
   所以还需要栈的结点含有返回地址字段r(分别用r=1，2，3以示区别)。
   (4)栈的结点定义和栈的存储方式
   struct NodeBag{    /*栈中元素的定义*/
       int s,n;
       int r;    /*r的值为1,2,3*/
       intk;
   };
   typedef struct NodeBag DataType;
   struct SeqStack{    /*顺序栈类型定义*/
       DataType s[MAXNUM];
       int t;    /*指示栈顶位置*/
   };
   typedefstruct SeqStack*PSeqStack;    /*顺序栈类型的指针类型*/
   (5)转换规律
   凡调用语句knap(s1，n1)均代换成：
   ①x.s=s1;/*引入一个变量x(struct NodeBag x)作为进出栈的缓冲*/
   x.n=n1;x.r=返回地址编号；
   ②push seq(st，x)；
   ③goto递归入口。
   将调用返回统一处理成：
   ①x=top_seq(st)；
   ②pop_seq(st)；
   ③根据x.r的值，进行相应处理：
   x.r=1，返回：
   x.r=2，继续处理1：
   x.r=3，继续处理2。
   (6)背包问题的非递归算法
   int nknap(int s,int n)
   {struct NodeBag x;
     PSeqStack st;
     int k：
     st=createEmptyStack_seq();
   /*entry0：初始调用入口*/
   x.s=s;x.n=n;x.r=1;
   push_seq(st,x);
     entry1：    /*递归调用入口*/
   x=top_seq(st);
   pop_seq(st);
   /*该函数与后面最接近的一个push_seq函数对是为了完成修改栈顶元素*/
   if(x.s=0)
   {x.k=TRUE;push_seq(st,x);goto exit2;}
   else if(x.s＜0(x.s＞0&&x.n＜1))
       {x.k=FALSE;push_seq(st,x);goto exit2;}
       else{push_seq(st,x);
       /*由于此处需要进一步往下递归,所以需再次入栈*/
           x.s=x.s-w[x.n-1];x.n=x.n-1;x.r=2;
           push_seq(st,x);  goto entry 1;}
       exit2：    /*返回处理*/
       x=top_seq(st);pop_seq(st);
       switch(x.r)
       {case 1：flee(st);return(x.k);
           case 2：goto L3;
           case 3：goto L4;)
       L3：    /*继续处理1*/
       if(x.k==TRUE)
           {x=top_seq(st);pop_seq(st);
           x.k=TRUE;push_seq(st,x);
           printf("result n=%d,w=%d",x.n,w[x.n-1]);goto exit2;}
       else{x=top_seq(st);x.s=x.s;
       x.n=x.n-1;x.r=3;push_seq(st,x);goto entry1;}
   L4;    /*继续处理2*/
   k=x.k;x=top_seq(st);pop_seq(st);
   x.k=k;push_seq(st,x);goto exit2;
   }