beibao.txt

程序中的beibao1函数采用了贪婪算法的另一种写法

#define K10
#define N10

#include <stdlib.h>
#include <conio.h>

void create(long array[],int n,int k)
{
   int i,j;
   array[0]=1;
   for(i=1;i<n;i++)
   {
      long t=0;
      for(j=0;j<i;j++)
            t=t+array[j];
      array[i]=t+random(k)+1;
   }
}
void output(long array[],int n)
{
   int i;
   for(i=0;i<n;i++)
   {
      if(i%5==0)
           printf("\n");
      printf("%14ld",array[i]);
   }
}

void beibao(long array[],int cankao[],long value,int count)
{
   int i;
   long r=value;
   for(i=count-1;i>=0;i--)
   {
      if(r>=array[i])
      {
            r=r-array[i];
            cankao[i]=1;
      }
      else
            cankao[i]=0;
   }
}

int beibao1(long array[],int cankao[],long value,int n)
{/*贪婪算法*/
   int i;
   long value1=0;
   for(i=n-1;i>=0;i--)/*先放大的物体，再考虑小的物体*/
      if((value1+array[i])<=value)/*如果当前物体可以放入*/
      {
          cankao[i]=1;/*1表示放入*/
          value1+=array[i];/*背包剩余容量减少*/
      }
      else
          cankao[i]=0;
   if(value1==value)
          return 1;
   return 0;
}

void main()
{
   long array[N];
   int cankao[N]={0};
   int cankao1[N]={0};
   int i;
   long value,value1=0;
   clrscr();
   create(array,N,K);
   output(array,N);
   printf("\nInput the value of beibao:\n");
   scanf("%ld",&value);
   beibao(array,cankao,value,N);
   for(i=0;i<N;i++)
      if(cankao[i]==1)
           value1+=array[i];
   if(value==value1)
   {
      printf("\nWe have got a solution,that is:\n");
      for(i=0;i<N;i++)
         if(cankao[i]==1)
        {
            if(i%5==0)
                printf("\n");
            printf("%13ld",array[i]);
        }
   }
   else
      printf("\nSorry.We have not got a solution.\n");
   printf("\nSecond method:\n");
   if(beibao1(array,cankao1,value,N)==1)
   {
     for(i=0;i<N;i++)
       if(cankao1[i]==1)
        {
            if(i%5==0)
                printf("\n");
            printf("%13ld",array[i]);
 }
   }
   else
      printf("\nSorry.We have not got a solution.\n");
}