Допустим, что у нас есть 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. Всё это нужно реализовать в программе, но важен, в основном, алгоритм или наводка на решение.
Итак, алгоритм
На входе список покупателей с диапазонами и список товаров с ценами.
Шаг 0: Создаем два класса: Покупатель и Товар. У каждого объекта Покупатель вычисляются такие параметры:
У каждого объекта Товар такие параметры:
На каждый товар отдельный объект, то есть несколько товаров с одинаковыми ценами - разные объекты.
Шаг 1. Убираем ненужное.
Убираем товары, на которые никто не претендует и покупателей, которые не претендуют ни на один товар.
Шаг 2. Первичное распределение.
Берем покупателя с наибольшим количеством товаров, на которые он претендует, и распределяем ему все эти товары
Берем следующего с наибольшим количеством, на которые он претендует, и распределяем ему их все (минус те, которые ушли к первому).
И так далее.
ЗАМЕЧАНИЕ: Распределение может быть вообще любым. Указанный выше метод может сократить время работы алгоритма.
В результате получится сортированный нумерованный список покупателей с распределенными товарами (у каких-то покупателей может быть 0 товаров). У покупателя 1 наибольшее количество, у покупателя N - наименьшее.
Шаг 3. Парное перераспределение
Возьмем покупателя 1 с количеством товаров Т.
Составляем пару с покупателем N с количеством товаров Тn.
Начинаем передавать товары по одному от 1 к N в произвольном порядке, если есть такие товары. Передача в паре заканчивается, если больше нет товаров к передаче, ИЛИ параметр Т <=Тn+1. Когда передача в паре 1:N закончилась, составляем пару покупателя 1 с покупателем N-1, повторяем. Пробегаем по всем парам 1:N, ...., 1:2.
Далее берем покупателя 2 и переходим в начало Шага 2, пробегаем все пары 2:N ...... 2:3.
Потом покупателя 3 и так далее.
ВАЖНО! Когда мы взяли покупателя К, пробегаются только его пары с БОЛЬШИМИ номерами, K:N, ..... K: (K-1). То есть с каждой итерацией количество пар уменьшается на одну.
ВАЖНО! Передача происходит только от покупателя с меньшим номером к покупателю с большим номером. Например, если мы взяли покупателя 3, и когда дошли до пары 3:5 оказалось, что у покупателя 5 на этот момент больше товаров, чем у 3, критерий Т <=Тn+1 считается выполненным и передачи не происходит, переходим к паре 3:4.
После того, как мы по очереди взяли всех покупателей 1,......, N-1 и на каждом прошли Шаг 3, работа алгоритма на Шаге 3 заканчивается.
Шаг 4. Сортировка
Теперь у некоторых покупателей параметр Т изменился. Проводим новую сортировку и снова формируем нумерованный список покупателей с распределенными товарами. У покупателя 1 наибольшее количество, у покупателя N - наименьшее. Переходим к Шагу 3.
Работа алгоритма заканчивается, когда на Шаге 3 не удалось сделать ни одной передачи товара.
Можно строго доказать, что этот алгоритм для любых входных параметров конечен, то есть вечного цикла не будет.