C Program to solve Knapsack Problem using Greedy Algorithm

# C Program to solve Knapsack Problem using Greedy Algorithm

31194
0
SHARE

C Program to solve Knapsack Problem using Greedy Algorithm : Below you can find how to implement knapsack problem using greedy method.

What actually Problem Says ?

1. Given a set of items, each with a weight and a value.
2. Determine the number of each item to include in a collection so that the total weight is less than a given limit and the total value is as large as possible.
3. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items.

C Program to solve Knapsack Problem using Greedy Algorithm :

```# include<stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {
float x[20], tp = 0;
int i, j, u;
u = capacity;

for (i = 0; i < n; i++)
x[i] = 0.0;

for (i = 0; i < n; i++) {
if (weight[i] > u)
break;
else {
x[i] = 1.0;
tp = tp + profit[i];
u = u - weight[i];
}
}

if (i < n)
x[i] = u / weight[i];

tp = tp + (x[i] * profit[i]);

printf("\nThe result vector is:- ");
for (i = 0; i < n; i++)
printf("%f\t", x[i]);

printf("\nMaximum profit is:- %f", tp);

}

int main() {
float weight[20], profit[20], capacity;
int num, i, j;
float ratio[20], temp;

printf("\nEnter the no. of objects:- ");
scanf("%d", &num);

printf("\nEnter the wts and profits of each object:- ");
for (i = 0; i < num; i++) {
scanf("%f %f", &weight[i], &profit[i]);
}

printf("\nEnter the capacityacity of knapsack:- ");
scanf("%f", &capacity);

for (i = 0; i < num; i++) {
ratio[i] = profit[i] / weight[i];
}

for (i = 0; i < num; i++) {
for (j = i + 1; j < num; j++) {
if (ratio[i] < ratio[j]) {
temp = ratio[j];
ratio[j] = ratio[i];
ratio[i] = temp;

temp = weight[j];
weight[j] = weight[i];
weight[i] = temp;

temp = profit[j];
profit[j] = profit[i];
profit[i] = temp;
}
}
}

knapsack(num, weight, profit, capacity);
return(0);
}```

OUTPUT:

```Enter the no. of objects:- 7

Enter the wts and profits of each object:-
2 10
3 5
5 15
7 7
1 6
4 18
1 3

Enter the capacity of knapsack:- 15

The result vector is:- 1.000000        1.000000        1.000000        1.000000
1.000000        0.666667        0.000000

Maximum profit is:- 55.333332```

Hope you like our . If you have any queries feel free to contact us.

SHARE
Previous articleC Program to Read a String of Text from File
Next articleC Program to Implement Stack
Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com