01bag.c

01背包问题c语言实现 01背包问题c语言实现

#include<stdio.h>
#define W 100
typedef int Datatype;
typedef struct
{
    Datatype z[W],o[W];
    int top,base;
} Dseqstack;
int s[W];
int M,N;
void print()
{
   int i;
   printf("Please input the counts( >0 ): ");
   scanf("%d",&N);
   printf("Please input the nummbers:\n");
   for(i=1;i<=N;i++)
   { 
       scanf("%d",&s[i]); 
   }
   printf("Please input the M:");
   scanf("%d",&M);
}
void paixu()
{
   int i,j,k;
   for(i=1;i<N;i++)
   { 
      s[0]=s[i];
      k=i;
      for(j=i+1;j<=N;j++)
      {
         if(s[0]>s[j])
         {
            s[0]=s[j];
            k=j;       
         }
      }
      if(k!=i)
      {
        s[k]=s[i];
        s[i]=s[0];
      } 
   }
   printf("Pai xu hou:\n");
   for(i=1;i<=N;i++)
   printf("  %-4d",s[i]);       
}
int knap(int m,int n,Dseqstack *r)
{
   if(m-s[n]==0)
   {
      r->z[r->top]=s[n];
      r->o[r->top]=n;
      r->top++;
   }
   else if(m-s[n]>0)
   {
      if(n>1)
      {
         r->z[r->top]=s[n];
         r->o[r->top]=n;
         r->top++;
         knap(m-s[n],n-1,r);
      }
      else
      {
         if(r->o[r->base]>2)
         {
            r->top--;
            n=r->o[r->top];
            m=m+r->z[r->top];
            knap(m,n-1,r);
         }
         else
            r->top=r->base;
      }
   }
   else
   {
      if(n>1)
        knap(m,n-1,r);
      else
      {
         if(r->o[r->base]>2)
         {
             r->top--;
             n=r->o[r->top];
             m=m+r->z[r->top];
             knap(m,n-1,r);
         }
         else
             r->top=r->base;
      }
   }
}
void main()
{
   int n,m;
   Dseqstack *r;
   textcolor(14);
   textbackground(1);
   clrscr();
   r=(Datatype *)malloc(W *sizeof(Datatype));
   r->top=r->base=0;
   print();
   n=N;
   m=M;
   paixu();
   knap(m,n,r);
   if(r->top==r->base)
      printf("\n\nNo suitable compose!!!\n");
   else
   {
      printf("\n\nThe suitable compose is:\n");
      while(r->top>0)
      {
          --r->top;
          printf("%-4d",r->z[r->top]);
      }
      printf("\n");
   }
   if(bioskey(0)!=283)
   main();
}