Untitled

 avatar
unknown
plain_text
2 months ago
1.3 kB
2
Indexable
import java.util.Arrays;
import java.util.Comparator;

class Item {
    int weight;
    int value;

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

public class FractionalKnapsack {
    public static double getMaxValue(Item[] items, int capacity) {
        // Sort items by value-to-weight ratio in descending order
        Arrays.sort(items, (a, b) -> Double.compare((double) b.value / b.weight, (double) a.value / a.weight));

        double maxValue = 0.0;
        for (Item item : items) {
            if (capacity >= item.weight) {
                // Take the whole item
                maxValue += item.value;
                capacity -= item.weight;
            } else {
                // Take the fraction that fits
                maxValue += (double) item.value * capacity / item.weight;
                break; // Knapsack is full
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(10, 60),
            new Item(20, 100),
            new Item(30, 120)
        };
        int capacity = 50;

        double maxValue = getMaxValue(items, capacity);
        System.out.println("Maximum value in Knapsack = " + maxValue);
    }
}
Editor is loading...
Leave a Comment