Knapsack Problem using Greedy Solution
Here you will learn program code to Implement Knapsack Problem using greedy solution in C programming language.
What is Knapsack Problem in DAA
The Knapsack Problem is like packing a bag with limited space. You have items with weights and values and a bag with a weight limit. Your goal is to choose the items that fit in the bag while maximizing their total value.
There are different versions: 0/1 (items go in or stay out), Fractional (you can take parts of items), and Multiple (many bags). It’s used in data analysis and other areas where you need to make the best choices with limited resources, like picking investments for maximum profit or selecting tasks within a time frame. It’s a tricky problem to solve efficiently.
C program to perform Knapsack Problem using Greedy Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | //C Program to Implement Knapsack Problem using Greedy Method #include<stdio.h> int main() { float weight[50],profit[50],ratio[50],Totalvalue,temp,capacity,amount; int i,j,num; printf("Enter number of items :"); scanf("%d",&num); for (i = 0; i < num; i++) { printf("\n\nEnter Weight and Profit for item[%d] :\n",i); scanf("%f %f", &weight[i], &profit[i]); } printf("\n\nEnter capacity of knapsack :\n"); 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; } } } printf("\nKnapsack Problem using Greedy Method :\n"); for (i = 0; i < num; i++) { if (weight[i] > capacity) break; else { Totalvalue = Totalvalue + profit[i]; capacity = capacity - weight[i]; } } if (i < num) Totalvalue = Totalvalue + (ratio[i]*capacity); printf("\nThe maximum value is :%f\n",Totalvalue); return 0; } |
Output
Read Also
Perform Travelling Salesman Problem
Find Minimum Spanning Tree using Kruskal’s Algorithm