Fractional Knapsack

class Pair {
    int value;
    int weight;

    Pair(int value, int weight) {
        this.value = value;
        this.weight = weight;
    }
}

class Solution {
    double fractionalKnapsack(List<Integer> val, List<Integer> wt, int capacity) {
        int n = wt.size();
        Pair[] pairs = new Pair[n];
        
        // Create Pair objects for each item
        for (int i = 0; i < n; i++) {
            pairs[i] = new Pair(val.get(i), wt.get(i));
        }
        
        // Sort items by value-to-weight ratio in descending order
        Arrays.sort(pairs, (a, b) -> {
            double ratioA = (double) a.value / a.weight;
            double ratioB = (double) b.value / b.weight;
            return Double.compare(ratioB, ratioA); // Sort in descending order
        });
        
        double ans = 0.0;
        
        // Iterate through the sorted items
        for (int i = 0; i < n; i++) {
            if (capacity == 0) {
                break;
            }
            
            if (pairs[i].weight <= capacity) {
                // Take the whole item
                ans += pairs[i].value;
                capacity -= pairs[i].weight;
            } else {
                // Take a fraction of the item
                double fraction = (double) capacity / pairs[i].weight;
                ans += pairs[i].value * fraction;
                capacity = 0; // Knapsack is full
            }
        }
        
        return ans;
    }
}