A C Program to implement Knapsack Problem.

#include<stdio.h>
#include<conio.h>

//int w[5]={0,2,3,4,5};
//int v[5]={0,3,4,5,6};
int w[10];
int v[10];
//int c[5][6];
int c[10][10];

void dp(int wr,int ni)
{       int ks[5],k;
int i,j;
for(i=0;i<(ni+1);i++)
{
for(j=0;j<(wr+1);j++)
{
c[i][0]=0;
c[0][j]=0;

}
}

for(i=1;i<(ni+1);i++)
{
      for(j=1;j<(wr+1);j++)
      {
if(j<w[i])
{
    c[i][j]=c[i-1][j];
}
else
{
    int t1,t2;

    t1=c[i-1][j];
    t2=v[i]+c[i-1][j-w[i]];

    if(t1>t2)
    c[i][j]=t1;
    else
    c[i][j]=t2;
}

      }
}//for ends
printf("       |");
for(j=0;j<(wr+1);j++)
printf(" %d |",j);
printf("\n");

printf("        ");
for(j=0;j<(wr+1);j++)
printf("____");
printf("\n");
for(i=0;i<(ni+1);i++)
{
printf("d[i]=%d |",w[i]);
for(j=0;j<(wr+1);j++)
{
printf(" %d |",c[i][j]);
}
printf("\n");
}

       i=ni;
       k=wr;
       while(i>0 && k>0)
       {
if(c[i][k]!=c[i-1][k])
{
ks[i]=1;
i--;
k=k-w[i];
}
else
{
ks[i]=0;
i--;
}
       }

       for(i=1;i<=ni;i++)
       {
printf("\nItem %d=%d",i,ks[i]);
       }
}

void main()
{
int N,ni,wr;
int i;
clrscr();
printf("Enter the number of items ");
scanf("%d",&ni);
w[0]=0;
v[0]=0;

for(i=1;i<=ni;i++)
{
      printf("\nEnter weight for %d ",i);
      scanf("%d",&w[i]);

      printf("Enter value for %d ",i);
      scanf("%d",&v[i]);
}

printf("\nEnter the weight required ");
scanf("%d",&wr);
clrscr();
dp(wr,ni);
getch();
}