Dynamic 0/1 Knapsack Problem

0/1 Knapsack Problem:

Problem Statement:

 Given n items from i1,i2,.....,in.
with weight w1,w2,......,wn.
and profit p1,p2,.....,pn.
 The Capacity of the bag is W.
Given a knapsack bag, we can either put an item completely in a bag or reject it you cannot put the item partially in the bag as done in Fractional Knapsack Problem ( Refer Fractional knapsack Problem: http://coders-domain.blogspot.in/2017/03/fractional-knapsack-problem.html )

Logic :we have to create a matrix where row=items+1 and columns=intial capacity +1;
         Put the entries in the first Row and first column as 0.
         The remaining entries to be filled by the following logic:
                a) if weight of the item i > current weight of bag
                      v[i,w]=v[i-1,w].
                b) if weight of item i <current weight of bag
                        v[i,w]=max(v[i-1,w],profit[i]+v[i-1,w-wt[i]])
       

code: #include<stdio.h>
#include<string.h>
int max(int i,int j)
{
if(i>j)
return i;
else
return j;
}

int main()
{
int n,j,i;
int c;
printf("enter number of items");
scanf("%d",&n);
int profit[n+1];
int weight[n+1];
for( i=1;i<n+1;i++)
{
printf("enter profit and weight of the item %d:",i);
scanf("%d%d",&profit[i],&weight[i]);
}
printf("enter capacity of knapsack");
scanf("%d",&c);
int knapsack[n+1][c+1];
for(i=0;i<n+1;i++)
{
for(j=0;j<c+1;j++)
{
if(i==0||j==0)
knapsack[i][j]=0;
else
{
if(weight[i]>j)
{
knapsack[i][j]=knapsack[i-1][j];
}
else
{
knapsack[i][j]=max(knapsack[i-1][j],profit[i]+knapsack[i-1][j-weight[i]]);
}
}
}
}
for(i=0;i<n+1;i++)
{
for(j=0;j<c+1;j++)
{
printf("%d\t",knapsack[i][j]);
}
printf("\n");
}
printf("the maximum profit earned is %d\n",knapsack[n][c]);
i=n;
j=c;
printf(" The items added are: \n");
//logic to print the items added
while(i>0 && j>0)
{
if(knapsack[i][j]!=knapsack[i-1][j])
{

printf("%d\t",i);
j-=weight[i];
i-=1;



}
else
i-=1;
}

}
/*output:
enter number of items4                                                                                                                                      
enter profit and weight of the item 1:100 3                                                                                                                  
enter profit and weight of the item 2:20 2                                                                                                                  
enter profit and weight of the item 3:60 4                                                                                                                  
enter profit and weight of the item 4:40 1                                                                                                                  
enter capacity of knapsack5                                                                                                                        
   items ->    0       1       2        3        4          5                (because capacity of bag is 5)
 |  columns
\ /       0        0       0       0        0         0          0                                                                                                                    
          1        0       0       0       100     100     100                                                                                                                  
           2       0       0       20      100     100     120                                                                                                                  
          3        0       0       20      100     100     120                                                                                                                  
          4        0       40      40      100     140     140                                                                                                                  
the maximum profit earned is 140                                                                                                                            
 The items added are:                                                                                                                                        
4       1                                                                                                                                          

*/