背包贪婪法程序.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

背包问题之贪婪算法求解C语言源代码[原创] 
关于背包问题描述请看http://bugeyes.blog.edu.cn/user1/20989/archives/2005/351526.shtml 。

其实原来的程序也是采用了贪婪算法，不过下面程序中的beibao1函数采用了贪婪算法的另一种写法，beibao函数是以前的代码，用来比较两种算法：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <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");
}
 -------------------------------------------------
背包问题解法C语言代码[原创] 
改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选每一个数值，使得选中的数值的和正好等于背包的容量。

代码思路：从最大的元素开始遍历超递增序列中的每个元素，若背包还有大于或等于当前元素值的空间，则放入，然后继续判断下一个元素；若背包剩余空间小于当前元素值，则判断下一个元素。

背包问题求解算法可用来设计密码系统，以后再写出来。

简单模拟如下：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <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;
   }
}

void main()
{
   long array[N];
   int cankao[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");

 

--------------------------------------------------
利用求组合的方法计算背包问题C语言源代码[原创] 
      求n个元素的所有组合，有很多方法，有一个方式是这样的：定义一个参考数组并设初值为全0，然后处理参考数组（从后向前扫描，若当前元素值为1则变为0，继续扫描；若当前元素值为0则变为1，然后退出扫描）。接下来根据参考数组输出n个元素（若对应的参考数组中元素值为1，则选择此元素，即输出）。

       可以利用这个求组合的方法计算背包问题，其实背包问题本来就可以看作n个元素的r组合。代码如下：

#define K 10
#define N 10

＃i nclude <stdlib.h>
＃i nclude <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 n)
{
   int i;
   int j;
   int cankao1[N]={0};
   long value1=0,value2=0;
   do
   {
      value2=0;
      for(j=n-1;j>=0;j--)/*处理参考数组*/
         if(cankao1[j]==0)
         {
            cankao1[j]=1;
            break;
         }
        else if(cankao1[j]==1)
             cankao1[j]=0;
      for(i=0;i<n;i++)/*计算当前选择方案*/
          if(cankao1[i]==1)
              value2+=array[i];
      if(value2<=value&&value2>value1)/*若当前选择方案可取*/
      {
           value1=value2;
           for(i=0;i<n;i++)/*记录选择方案*/
              cankao[i]=cankao1[i];
      }
   }while(j>=0);
}

void main()
{
   long array[N];
   int cankao[N]={0};
   int i;
   long value;
   clrscr();
   create(array,N,K);
   output(array,N);
   printf("\nInput the value of beibao:\n");
   scanf("%ld",&value);
   beibao(array,cankao,value,N);
   printf("\nThe answer is:\n");
   for(i=0;i<N;i++)
      if(cankao[i]==1)
         printf("%8ld",array[i]);
}