背包問題解法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");
}