//Fractional Knapsack import java.util.*; class Item { int profit; int weight; float ratio; Item(int profit, int weight) { this.profit = profit; this.weight = weight; ratio = (float) (profit / weight); } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int capacity = sc.nextInt(); Item[] items = new Item[N]; for (int i = 0; i < N; i++) { int profit = sc.nextInt(); int weight = sc.nextInt(); items[i] = new Item(profit, weight); } float profit = fractionalKnapsack(items, N, capacity); System.out.println("Total profit: " + profit); } public static float fractionalKnapsack(Item[] items, int N, int capacity) { Arrays.sort(items, Comparator.comparingDouble((Item item) -> item.ratio).reversed()); float totalProfit = 0; int currentWeight = 0; for (Item item : items) { if (currentWeight + item.weight <= capacity) { currentWeight += item.weight; totalProfit += item.profit; } else { int remaining = capacity - currentWeight; totalProfit += item.profit * ((float) remaining / item.weight); break; } } return totalProfit; } } /* Sample Test Case: Input: 4 50 60 10 100 20 120 30 80 40 Output: Total profit: 240.0 */
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter