Knapsack problem (using dynamic programming) in C.

 

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]

Related Post

Leave a Reply

Your email address will not be published. Required fields are marked *