Допустим, что у нас есть 100 товаров по фиксированной цене от 1 до 100 рублей. Разбиение может быть и 100 товаров по 1 рублю, а может быть и 100 товаров по разным ценам (от 1 до 100) .
Также есть несколько покупателей, готовых купить этот товар.
Покупатели привередливые и каждый хочет купить товар в каком-то определённом диапазоне. Например, один из покупателей хочет покупать товары только от 50 до 100 рублей (без разницы за сколько, но в этом диапазоне), другие 3 хотят купить товар от 10 до 80 рублей, следующие 2 могут покупать товары от 1 до 100 и так далее.
Некоторые покупатели могут уйти без покупок, а некоторые купят несколько товаров из своего диапазона.
Если товар с такой ценой не входит ни в один диапазон ни одного покупателя, то такой товар не будет продан (это нормально).
Вопрос. Как оптимально разделить товары между покупателями в их диапазонах, чтобы каждый покупатель имел на руках некое среднее значение.
Например. Первый (1) и Второй (2) покупатели имеют диапазон 20-50. А третий имеет диапазон 1-100. Допустим, что на каждую цену от 1 до 100 у нас есть по 1 товару. Тогда распределение будет такое: Первый и второй будут вместе иметь 30 товаров на двоих, значит по 15 каждому. А все остальные товары - 99-30=69 заберёт третий т.к больше нет покупателей в этом диапазоне.
P.S. Всё это нужно реализовать в программе, но важен, в основном, алгоритм или наводка на решение.
Ну хорошо, попробую предложить алгоритм. Но сначала уточню формулировку:
Формулировка автора в условиях несколько размыта:
"Как оптимально разделить товары между покупателями в их диапазонах, чтобы каждый имел на руках некое среднее значение"
Что за "некое среднее значение"? Непонятно. Превращу в точную формулировку:
"Как разделить товары между покупателями в их диапазонах так, чтобы для любых пар покупателей, таких, что если разница в количестве товаров у такой пары была бы не меньше 2, нельзя было бы передать один из товаров от покупателя с большим количеством товаров покупателю с меньшим количество товаров".
Звучит запутано, а что делать.
Максим, я правильно уточнил формулировку? Не надо меня дизлайкать, если неправильно, лучше прокомментируйте.