Knapsack Problem

4. Implement 0/1 Knapsack problem using Dynamic Programming.

#include<stdio.h>
#include<stdlib.h>

void displayinfo();
void knapsack();
void optimal();

int i,j,x[10],n,m,v[10][10],w[10],p[10],item=0;
void main()
{
 printf("\n\n********KNAPSACK PROBLEM *************\n\n");
 printf("\n\n Enter the total number of items:\n");
 scanf("%d",&n);
 printf("\n\n Enter the weight of each item:\n\n");
 for(i=1;i<=n;i++)
       scanf("%d",&w[i]);
 printf("\n\n Enter the profit of each ittem:\n\n");
 for(i=1;i<=n;i++)
       scanf("%d",&p[i]);
 printf("\n\nEnter the knapsack capacity:\n\n");
 scanf("%d",&m);
 displayinfo();
 knapsack();
 printf("\n\n The content of the knapsack table are \n");
 for(i=0;i<=n;i++)
   {
     for(j=0;j<=m;j++)
       {
          printf("%d\t",v[i][j]);
       }
     printf("\n");
   }
 optimal();
}
void displayinfo()
 {
  printf("\n\nEnterd information about knapsack problem are\n");
  printf("\nITEM\tWEIGHT\tPROFIT\n");
  for(i=1;i<=n;i++)
      printf("%d\t%d\t%d\n",i,w[i],p[i]);
  printf("capacity=%d\n\n",m);
 }
void knapsack()
 {
  for(i=0;i<=n;i++)
   {
    for(j=0;j<=m;j++)
     {
      if(i==0||j==0) 
              v[i][j]=0;
      else if(j<w[i])  
              v[i][j]=v[i-1][j];
      else   
              v[i][j]=max(v[i-1][j],(v[i-1][j-w[i]]+p[i]));
     }
   }
 }
void optimal()
 {
  int i=n,j=m;
  while(i!=0&&j!=0)
   {
    if(v[i][j]!=v[i-1][j])
         {
           x[i]=1;
           j=j-w[i];
         }
     i=i-1;
   }
   printf("\n\n Optimal solution is %d\n\n",v[n][m]);
   printf("selected items are:");
   for(i=1;i<=n;i++)
   if(x[i]==1)
    {
     printf("%d,",i);
     item=1;
    }
   printf("\b\b");
   if(item==0)
   printf("NIL\n\t sorry!No item can be placed in knapsack\n");
   printf("\n***************************************\n");
 }
int max(int a,int b)
 {
   if(a>b)
     return a;
   else
     return b;
 }



OUTPUT:

Enter the total number of items: 4
Enter the weight of each item: 2  3  1  2
Enter the profit of each item:12  10  15  20
Enter the knapsack capacity:5



Enter the total number of items: 2
Enter the weight of each item: 10  20
Enter the profit of each item:30  25
Enter the knapsack capacity:5