Knapsack

//THIS IS SOMEWHAT WRONG ONLY PARTIALLY CORRECT

#include <stdio.h>
#include <stdlib.h>

// Define the structure to hold item details (profit, weight, and ratio)
typedef struct {
    int profit;
    int weight;
    float ratio; // profit-to-weight ratio
} Item;

// Comparator function for sorting items by profit-to-weight ratio
int compare(const void *a, const void *b) {
    Item *item1 = (Item *)a;
    Item *item2 = (Item *)b;
    
    // Sort in decreasing order of ratio
    if (item1->ratio < item2->ratio) 
        return 1;
    else if (item1->ratio > item2->ratio) 
        return -1;
    return 0;
}

// Function to solve the fractional knapsack problem
float knapsack(int m, Item items[], int n) {
    // Sort the items in decreasing order of profit-to-weight ratio
    qsort(items, n, sizeof(Item), compare);

    float totalProfit = 0.0; // Total profit earned by including items in the knapsack
    int currentWeight = 0;   // Current weight in the knapsack

    for (int i = 0; i < n; i++) {
        if (currentWeight + items[i].weight <= m) {
            // If the item can be fully added to the knapsack
            currentWeight += items[i].weight;
            totalProfit += items[i].profit;
        } else {
            // Otherwise, take the fractional part of the item
            int remainingWeight = m - currentWeight;
            totalProfit += items[i].profit * ((float)remainingWeight / items[i].weight);
            break;  // Knapsack is full
        }
    }

    return totalProfit;
}

int main() {
    int n, m;

    // Input: number of items and knapsack capacity
    printf("Enter the number of items: ");
    scanf("%d", &n);
    printf("Enter the capacity of the knapsack: ");
    scanf("%d", &m);

    Item items[n];

    // Input: profit and weight of each item
    printf("Enter profit and weight for each item:\n");
    for (int i = 0; i < n; i++) {
        printf("Item %d - Profit: ", i + 1);
        scanf("%d", &items[i].profit);
        printf("Item %d - Weight: ", i + 1);
        scanf("%d", &items[i].weight);

        // Calculate the profit-to-weight ratio for each item
        items[i].ratio = (float)items[i].profit / items[i].weight;
    }

    // Calculate the maximum profit that can be earned
    float maxProfit = knapsack(m, items, n);
    printf("Maximum profit that can be earned: %.2f\n", maxProfit);

    return 0;
}