Не могу понять алгоритм решения
В общем, пытаюсь решить одну задачу и не могу найти алгоритм её решения.
Вот условие и пример вывода с пояснением:
Я пробую определить формулу для вычисления, но ничего не получается. Сначала исходил из того, что согласно условия задачи стоимость доставки не зависит от количества доставляемого товара. Тогда наиболее выгодный товар с наименьшей стоимостью delivery, но другие параметры тоже влияют на выбор наиболее выгодного товара. Пробовал вычислить стоимость доставки одной единицы товара delivery : amount*count, но ничего это не дало. Может надо найти коэффициент какой-то. Вот какой - не могу понять. Натолкните на решение этой задачи.
Условие задачи текстом:
Компания решила оптимизировать поставки продукции. У каждого из отделов по производству в наличии есть ограниченное количество партий готовой продукции, количество партий count: в партии или 50 штук, или 100, или 500, или 1000 штук - хранится в amount, цены указаны в price. Продукция у всех отделов одинаковая. Сумма доставки в центральный магазин у каждого из отделов разная, но у всех она не зависит от количества доставляемого товара - хранится в delivery. Необходимо рассчитать оптимальную поставку n штук продукции.
Примечание:
стоимость продукции и доставки не может совпадать у разных отделов мы не можем купить дробное число партий, то есть у последнего поставщика покупаем всю партию, несмотря на то, что нам нужна часть На входе:
n - необходимое количество продукции
price - массив цен за одну партию продукции
amount- массив с количеством продукции в одной партии продукции
count - массив с количеством партий продукции в наличии
delivery - массив стоимости доставки для всех поставщиков, независимо от количества купленных партий продукции
На выходе: строка - номера поставщиков через запятую (поставщики нумеруются с 0), у которых мы будем заказывать продукцию, в порядке приоритета. То есть у одного (наиболее выгодного) купили всё, переходим к другому и так до конца, пока не купим достаточное количество n
Пример:
n=1000
price=[100, 200, 300, 400]
amount=[50, 100, 500, 100]
count=[4, 5, 7, 3]
delivery=[0, 100, 5000, 1000]
getResult(n, price, amount, count, delivery) → 0,1,3 // сначала покупаем у 0-го поставщика 4 * 50 продукции, затем у 1-го 5 * 100, остальное покупаем у 3-го
Ответы (1 шт):
Моё решение ниже. Не проходит 4-ый тест, мне кажется там тест неверный, вручную даже считал. Алгоритм состоит в том, чтобы вычислить цену товара за единицу с учетом доставки. Формула такая S=(p*tA+d)/tA, где p-price, tA - total amount (=amount но не более n) максимальное нужное число товара, tC - total count (=n/amount с округлением вверх) максимально нужное число партий. К тому же нужно учитывать, что при покупке последней партии весь товар не нужен, поэтому нужно пересчитать единицу стоимости товара, для этого цикл while и строка: n -= amount.get(provider) * count.get(provider);
public static String getResult(int n, List<Integer> price, List<Integer> amount, List<Integer> count, List<Integer> delivery) {
int products = n;
int maxAmount = 0;
int provider;
List<Integer> result = new ArrayList<>();
List<Integer> providers = new ArrayList<>();
Map<Integer, Double> costPerUnit = new HashMap<>();
StringBuilder sb = new StringBuilder();
while (true) {
for (int i = 0; i < price.size(); i++) {
if (result.contains(i)) {
costPerUnit.put(i, Double.MAX_VALUE);
continue;
}
int totalCount;
double needCount = (double) n / (double) amount.get(i);
if (needCount > count.get(i)) {
totalCount = count.get(i);
} else {
totalCount = (int) Math.ceil(needCount);
}
int totalAmount = amount.get(i) * count.get(i);
if (totalAmount > n) {
totalAmount = n;
}
double cost = ((double) price.get(i) * totalCount + (double) delivery.get(i)) / (double) totalAmount;
costPerUnit.put(i, cost);
}
costPerUnit.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(e -> providers.add(e.getKey()));
provider = providers.get(0);
maxAmount += amount.get(provider) * count.get(provider);
if (maxAmount >= products || result.size() == price.size() - 1) {
result.add(provider);
break;
} else {
result.add(provider);
}
providers.clear();
n -= amount.get(provider) * count.get(provider);
}
for (Integer r : result) {
sb.append(r).append(",");
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}