knapsac1.c

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

/*简单背包问题的递归实现*/
#define maxsize 50
#include <stdio.h>
int w[maxsize];  /*按照从小到大的顺序存放各物品的重量值*/
int knapsack(int s,int m)
{ /*在w1,w2,……wm中选出若干件物品，使其重量总和为s。若解存在返回1，否则返回0*/
  int s1,b;
  if (s==0) return(1);  /*寻找问题的解成功*/
  else if ((s<w[1]) ||(m==0))  return(0);  /*寻找问题的解不成功*/
       else {
              do
                {
                  s1=w[m]; m--; /*考虑wm选择的可能性*/
                  b=knapsack(s-s1,m);
                 }
               while ((m!=0) && (!b));
              if (!b) return(0);  
              else {  /*选择wm成功，并将其打印输出*/
                     printf("\n%d",s1);
                     return(1);
                    }
             }
}
main()
{
   int n,s,i,success;
   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]);
   success=knapsack(s,n);
   if (!success) printf("error!");
 }