Stepik - 4.1. Непрерывный рюкзак
Описание задачи
Первая строка содержит количество предметов 1≤n≤10^3 и вместимость рюкзака 0≤W≤2⋅10^6. Каждая из следующих nn строк задаёт стоимость 0≤ci≤2⋅10^6 и объём 0<wi≤2⋅10^6 предмета (n, W, c, w) — целые числа). Выведите максимальную стоимость частей предметов (от каждого предмета можно отделить любую часть, стоимость и объём при этом пропорционально уменьшатся), помещающихся в данный рюкзак, с точностью не менее трёх знаков после запятой.
Надежный шаг
Надежным шагом является выбор максимального кол-ва предметов с наибольшей стоимостью удельной единицы. Сначала нужно отсортировать предметы в порядке уменьшения стоимости удельной единицы а после брать по максимуму
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* Main
*
* @author Vladislav Sidlyarevich <vlsidlyarevich@gmail.com>
* Created on 3/7/21.
*/
public class Main {
private List<Item> items = new ArrayList<>();
public void run() {
Scanner scanner = new Scanner(System.in).useDelimiter("\n");
String[] input = scanner.nextLine().split("\\s+");
int itemsSize = Integer.parseInt(input[0]);
int freeSpace = Integer.parseInt(input[1]);
for (int i = 0; i < itemsSize; i++) {
String[] item = scanner.nextLine().split("\\s+");
items.add(new Item(Integer.parseInt(item[0]), Integer.parseInt(item[1])));
}
scanner.close();
Double result = calculate(freeSpace);
System.out.println(result);
}
private Double calculate(int freeSpace) {
//Отсортировать предметы по стоимости удельной единицы
Collections.sort(items);
double result = 0;
for (Item item: items) {
if(freeSpace == 0) return result;
if(freeSpace >= item.quantity) {
result+=item.price;
freeSpace-=item.quantity;
} else {
//Предмет больше чем места, берем часть
result += freeSpace * item.calculatePricePerQuantity();
freeSpace = 0;
}
}
return result;
}
public static void main(String[] args) {
Main main = new Main();
main.run();
}
private class Item implements Comparable<Item> {
double price;
double quantity;
public Item(final int price, final int quantity) {
this.price = price;
this.quantity = quantity;
}
double calculatePricePerQuantity() {
return price/quantity;
}
@Override
public int compareTo(final Item o) {
if (this.calculatePricePerQuantity() == o.calculatePricePerQuantity()) return 0;
return this.calculatePricePerQuantity() > o.calculatePricePerQuantity() ? -1 : 1;
}
}
}