Task-4
Implement Fractional Knapsack Algorithm
Algorithm:
Algorithm Sort(p, w, n){
  int r[n], index[n];
  int p[n], w[n];
  
  for i := 1 to n
    r[i] := p[i] / w[i];
  
  for i := n to n do{
    j := i;
    for k := i + 1 to n do
      if (r[k] <= r[j]) then 
	j := k;
    if(j!-i){
     index[i] := j;
     t := r[i];
     r[i] := r[j];
     r[j] := t;
    }
  }
  
  for i := 1 to n
  {
    p[i] := p[index[i]];
    w[i] := w[index[i]];
  }
}
Program:
#include <stdio.h>

void knapsack(int n, float weight[], float profit[], float capacity) {
    float tp = 0;
    int i, u;
    u = capacity;
    for (i = 0; i < n; i++) {
        if (weight[i] > u)
            break;
        else {
            tp = tp + profit[i];
            u = u - weight[i];
        }
    }
    if (i < n)
        tp = tp + (u / weight[i] * profit[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:-\n");
    for (i = 0; i < num; i++) {
        scanf("%f %f", &weight[i], &profit[i]);
    }

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

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

    // Sort items by profit/weight ratio in descending order
    for (i = 0; i < num; i++) {
        for (j = i + 1; j < num; j++) {
            if (ratio[i] < ratio[j]) {
                // Swap ratios
                temp = ratio[j];
                ratio[j] = ratio[i];
                ratio[i] = temp;

                // Swap weights and profits to keep arrays aligned
                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:- 5
Enter the wts and profits of each object:-
4 12
1 2
2 2
1 1
4 10
Enter the capacity of knapsack:- 15
Maximum profit is:- 17.333334

=== Code Execution Successful ===