Untitled
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