Fractional Knapsack algorithm in DAA
Here you will learn Fractional Knapsack problem in c programming.
The Fractional Knapsack algorithm in DAA is a greedy algorithm used to optimize the selection of items with fractional weights and values to maximize the total value, fitting within a fixed capacity knapsack.
Program code of Fractional Knapsack algorithm in DAA
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 57 58 59 | # 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 weights 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
