0-1背包.c

0-1背包问题的解决

#include"stdio.h"
int main()
{    int i,j,k,c,n,jmax,m[11][11],x[11],w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6};
     n=5;c=10;
     for(i=0;i<=n;i++)
         for(j=0;j<=c;j++)
         m[i][j]=0;
     jmax=(w[n]-1)<c?(w[n]-1):c;
     for(j=0;j<=jmax;j++) m[n][j]=0;
     for(j=w[n];j<=c;j++) m[n][j]=v[n];
     for(i=n-1;i>1;i--)
     {    jmax=(w[i]-1)<c?(w[i]-1):c;
          for(j=0;j<=jmax;j++)
              m[i][j]=m[i+1][j];
          for(j=w[i];j<=c;j++)
              m[i][j]=m[i+1][j]>(m[i+1][j-w[i]]+v[i])?m[i+1][j]:(m[i+1][j-w[i]]+v[i]);
     }
     m[1][c]=m[2][c];
     if(c>=w[1])
          m[1][c]=m[1][c]>(m[2][c-w[1]]+v[1])?m[1][c]:(m[2][c-w[1]]+v[1]);
     printf("        子问题的解用下列矩阵表示：\n\n");
     for(i=1;i<=n;i++)
     {    printf("        ");
          for(j=0;j<=c;j++)
          {    printf("%d",m[i][j]);
               printf(m[i][j]<10?"   ":"  ");
          }
          printf("\n");
     }
     for(i=1;i<n;i++)
         if(m[i][c]==m[i+1][c]) x[i]=0;
         else 
         {   x[i]=1;
             c-=w[i];
         }
      x[n]=(m[n][c])?1:0;
      printf("\n        结果为：");
      for(i=1;i<=n;i++) printf("%d  ",x[i]);
      printf("\n        表示选择1，2，5号物品\n");
      system("pause"); 
}