背包问题解法c语言代码.txt

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

背包问题解法C语言代码[原创] 
改进的背包问题：给定一个超递增序列和一个背包的容量，然后在超递增序列中选（只能选一次）或不选每一个数值，使得选中的数值的和正好等于背包的容量。

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

背包问题求解算法可用来设计密码系统，如下。

        0-1背包问题的解是某些物体的“选”与“不选”，设置一个与物体数目一样多的参考数组，如果选择某物体，则把其对应的参考数组元素设置为1，否则设置为0。而这个参考数组中的元素也可以看作是一个数的二进制编码，因此，可以用来实现加密和解密。如通信双方约定好一些物体的重量（超递增序列）为：

       1，2，5，10，21，43，91，185

     如果发送方要发送字符‘A’，则把其转换为二进制数01000001，然后与物体重量数组相乘，得到整数187（加密），把187发送给接收方，接收方把187看作背包的容量，而把事先约定好的一些数看作物体重量，进行背包问题求解，则得到01000001，将其转换为整数65，对应字符为‘A’（解密）。


简单模拟如下：

#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");
}