#include <stdio.h>
#include <stdlib.h>
struct Activity {
    int start;
    int finish;
};

int compare(const void *a, const void *b) {
    return ((struct Activity *)a)->finish - ((struct Activity *)b)->finish;
}

void printMaxActivities(struct Activity arr[], int n) {
    qsort(arr, n, sizeof(arr[0]), compare);

    printf("Following activities are selected:n");
    int i = 0;
    printf("Activity %d: (%d, %d)\n", i, arr[i].start, arr[i].finish);

    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].finish) {
            printf("Activity %d: (%d, %d)\n", j, arr[j].start, arr[j].finish);
            i = j;
        }
    }
}

int main() {
    struct Activity arr[] = {% raw %}{{0, 6}, {1, 4}, {3, 5}, {5, 7}, {5, 9}, {8, 9}}{% endraw %};
    int n = sizeof(arr) / sizeof(arr[0]);
    printMaxActivities(arr, n);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
struct Item {
    int value;
    int weight;
};

int compare(const void *a, const void *b) {
    double r1 = (double)((struct Item *)a)->value / ((struct Item *)a)->weight;
    double r2 = (double)((struct Item *)b)->value / ((struct Item *)b)->weight;
    return (r1 > r2) ? -1 : (r1 < r2) ? 1 : 0;
}

double fractionalKnapsack(struct Item arr[], int W, int n) {
    qsort(arr, n, sizeof(arr[0]), compare);
    double totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        } else {
            totalValue += arr[i].value * ((double)W / arr[i].weight);
            break;
        }
    }
    return totalValue;
}

int main() {
    
    struct Item arr[] = {% raw %}{{60, 10}, {100, 20}, {120, 30}}{% endraw %};
    
    int W = 50;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum value in Knapsack = %.2fn", fractionalKnapsack(arr, W, n));
    return 0;
}