01 #include <stdio.h>
02 
03 int matrix[100][100] = {0};
04 int picks[100][100] = {0};
05 
06 int max(int,int);
07 int knapsack01(int,int,int [],int []);
08 void showPickedItems(int,int,int []);
09 
10 int main()
11 {
12     int n;
13     int knapsackSize;
14     int weights[50];
15     int profits[50];
16 
17     int i;
18 
19     printf("n0/1 Knapsack Problem");
20     printf("n(using Dynamic Programming)");
21 
22     printf("nnEnter number of objects : ");
23     scanf("%d",&n);
24 
25     printf("nEnter weights :n");
26     for(i=0; i<n; i++)
27     {
28         printf("For object [%d] : ",i+1);
29         scanf("%d",&weights[i]);
30     }
31 
32     printf("nEnter profits :n");
33 
34     for(i=0; i<n; i++)
35     {
36         printf("For object [%d] : ",i+1);
37         scanf("%d",&profits[i]);
38     }
39 
40     printf("nEnter knapsack size : ");
41     scanf("%d",&knapsackSize);
42 
43 
44     printf("Max Profit Earned = %dn",knapsack01(n,knapsackSize,weights,profits));
45     printf("Items Picked : ");
46     showPickedItems(n,knapsackSize, weights);
47 
48     return 0;
49 }
50 
51 int max(int a,int b)
52 {
53     if(a>b)
54         return a;
55     else
56         return b;
57 }
58 
59 int knapsack01(int n, int size, int weights[], int profits[])
60 {
61     int i,j;
62     int v1,v2;
63 
64     for (i=1; i<=n; i++)
65     {
66         for (j=0; j<=size; j++)
67         {
68             if (weights[i-1]<=j)
69             {
70                 v1= matrix[i-1][j];
71                 v2= profits[i-1]+matrix[i-1][j-weights[i-1]];
72 
73                 matrix[i][j] = max(v1,v2);
74 
75                 if (v2>v1)
76                     picks[i][j]=1;
77                 else
78                     picks[i][j]=-1;
79             }
80             else
81             {
82                 picks[i][j] = -1;
83                 matrix[i][j] = matrix[i-1][j];
84             }
85         }
86     }
87 
88     return matrix[n][size];
89 
90 }
91 
92 void showPickedItems(int item, int size, int weights[])
93 {
94 
95     while (item>0)
96     {
97         if (picks[item][size]==1)
98         {
99             printf("n Object [%d] ",item);
100             item--;
101             size -= weights[item];
102         }
103         else
104         {
105             item--;
106         }
107     }
108 
109     printf("n");
110 
111 }

 
 OUTPUT :
 
 
 0/1 Knapsack Problem
 (using Dynamic Programming)
 
 Enter number of objects : 4
 
 Enter weights :
 For object [1] : 10
 For object [2] : 15
 For object [3] : 6
 For object [4] : 9
 
 Enter profits :
 For object [1] : 2
 For object [2] : 5
 For object [3] : 8
 For object [4] : 1
 
 Enter knapsack size : 30
 Max Profit Earned = 14
 Items Picked :
  Object [4]
  Object [3]
  Object [2]