动态规划解决01背包问题

#include<stdio.h>
void knapsack(int W,int n);
int w[4]={0,3,4,5},p[4]={0,4,5,6},flag[4];
int c[4][11];
void main()
{
 int i,j;
 knapsack(10,3);
 for(i=0;i<4;i++)
      for(j=0;j<11;j++)
         {
          printf("%3d ",c[i][j]);
             if(j==10)printf("\n");
         }
   for(i=1;i<4;i++)
  printf("%3d ",flag[i]);

}
void knapsack(int W,int n)
{
 int i,j;
 for(i=0;i<=n;i++)
      for(j=0;j<=W;j++)
           c[i][j]=0;
   for(i=0;i<=3;i++)
    for(j=0;j<=10;j++)
    {
     if(w[i]<=j) 
    {
      if(c[i-1][j]>=c[i-1][j-w[i]]+p[i])
       c[i][j]=c[i-1][j];
      else c[i][j]=c[i-1][j-w[i]]+p[i];
    }
     else c[i][j]=c[i-1][j];
    }
 for(i=n,j=W;i>=1;i--)
  if(c[i][j]>c[i-1][j])
  {flag[i]=1;j=j-w[i];}
 else flag[i]=0;
}