knap sack

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class Item {
    int id;
    int weight;
    int profit;
    double cost;

    public Item(int id, int weight, int profit) {
        this.id = id;
        this.weight = weight;
        this.profit = profit;
        this.cost = (double) profit / weight;
    }
}

public class FractionalKnapsack {

    public static double fractionalKnapsack(Item[] items, int capacity, float[] solutionVector) {
        Arrays.sort(items, Comparator.comparingDouble(item -> -item.cost));

        double totalProfit = 0.0;
        for (Item item : items) {
            if (capacity == 0) {
                break;
            }
            if (item.weight <= capacity) {
                totalProfit += item.profit;
                capacity -= item.weight;
                solutionVector[item.id - 1] = 1.0f;
            } else {
                float fraction = (float) capacity / item.weight;
                totalProfit += item.profit * fraction;
                solutionVector[item.id - 1] = fraction;
                capacity = 0;
            }
        }
        return totalProfit;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of items: ");
        int n = scanner.nextInt();
        System.out.print("Enter the capacity of the knapsack: ");
        int capacity = scanner.nextInt();

        Item[] items = new Item[n];
        float[] solutionVector = new float[n];

        for (int i = 0; i < n; i++) {
            System.out.print("Enter weight and profit of item " + (i + 1) + ": ");
            int weight = scanner.nextInt();
            int profit = scanner.nextInt();
            items[i] = new Item(i + 1, weight, profit);
            solutionVector[i] = 0.0f;
        }

        double maxProfit = fractionalKnapsack(items, capacity, solutionVector);
        System.out.printf("Maximum profit in Knapsack = %.2f\n", maxProfit);

        System.out.print("Solution vector (ID: fraction included): ");
        for (int i = 0; i < n; i++) {
            System.out.printf(" %d: %.2f ", items[i].id, solutionVector[i]);
        }
        System.out.println();

        
    }
}