knapsac2.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/*简单背包问题的非递归实现*/
#define MAXSIZE 50
#define MAXS 25
#include <stdio.h>
int w[MAXSIZE];  /*所有物品的重量按从小到大的顺序存储于w中*/
void knapsack(int s,int m)
{
  typedef struct {
         int s;   /*存储被选物品的重量*/
         int m;   /*存储被选物品的编号*/
    } stackelem;
   stackelem stack[MAXS];  /*用于记录回溯点的堆栈*/
   int i,t,top,nofail;     /*top为栈顶指针，nofail为求解成功的标志*/
   t=0; top=0; nofail=1;   /*变量t用于记录已被选的物品重量总和*/
   while ((s!=t) && nofail)
     {
       if ((s>=t+w[1])&&(m>0)) 
         {   /*表示至少还有一个物品被选的可能*/
           top++; stack[top].s=w[m]; /*选择wm并将它进栈*/
           stack[top].m=m; 
           t=t+w[m]; --m;
          }
        else  /*表示刚才一个选择不合适，需进行回溯*/
          {
            if (m==0) {
                 t=t-stack[top].s; --top;
                       }
             if (top<1)  nofail=0;  /*栈已为空，求解失败*/
             else {/*表示栈顶元素被选不合适，从其前一个元素开始重新试探*/
                   m=stack[top].m-1;
                   t=t-stack[top].s; --top;
                   }
             }
       }
   if (s==t)  /*求解成功，将解输出*/
       for(i=1;i<=top;++i) 
         printf("\n%d\n", stack[i].s);
   else printf("there is no any selection!");/*求解失败*/
  }    
 main()
{
   int n,s,i;
   printf("\nplease input the value n and s:\n");
   scanf("%d%d",&n,&s);
   printf("\nplease input the w[n]:\n");
   for (i=1;i<=n;++i)
       scanf("%d",&w[i]);
   knapsack(s,n);
 }