Найти лучший способ купить p Продукт из лимита x Поставщики

Ответ 1

Эта проблема эквивалентна неметрической проблеме k-center (города = продукты, склады = поставщики), которая NP-hard.

Я бы попробовал смешанное целочисленное программирование. Здесь одна формулировка.

minimize c(i, j) y(i, j)  # cost of all of the orders
subject to
for all i: sum over j of y(i, j) = 1  # buy each product once
for all i, j: y(i, j) <= z(j)  # buy products only from chosen vendors
sum over j of z(j) <= x  # choose at most x vendors
for all i, j: 0 <= y(i, j) <= 1
for all j: z(j) in {0, 1}

Интерпретация переменных заключается в том, что i является продуктом, j является поставщиком, c(i, j) является стоимостью продукта i от поставщика j, y(i, j) is 1, если мы покупайте продукт i у поставщика j и 0 в противном случае z(j) 1 мы покупаем у поставщика j вообще и 0 в противном случае.

Есть много бесплатных программных программных программ с целыми числами.

Ответ 2

Неправильно, как показано в @Per, структура не имеет оптимальной субструктуры

Мои предположения следующие: из главной таблицы вам нужно создать дополнительный список, который имеет только "x" столбцы поставщиков, а "Лучшая цена" - это "Сумма" всех цен.

Используйте подход с динамическим программированием Вы определяете две функции: Picking (i,k) и NotPicking(i,k). То, что это означает, - это лучшее с возможностью выбора поставщиков от 1,.. я с максимальным количеством поставщиков.

Picking (1,_) = Sum(All prices)
NotPicking (1,_) = INF
Picking (_,0) = INF
NotPicking (_,0) = INF

Picking (i,k) = Min (Picking(i-1,k-1) + NotPicking(i-1,k-1)) - D (The difference you get because of having this vendor)
NotPicking (i,k) = Min (Picking(i-1,k) + NotPicking(i-1,k))

Вы просто решаете его для i от 1 до V и k от 1 до X

Вы вычисляете разницу, поддерживая для каждого выбора весь список продуктов и вычисляя разницу.

Ответ 3

EDIT: венгерский алгоритм не является ответом на ваш вопрос, если вы не хотели устанавливать ограничения на поставщиков.

Алгоритм, который вы ищете, Венгерский алгоритм.

Существует много доступных реализаций в Интернете.

Ответ 4

Как насчет использования жадного подхода. Поскольку у вас есть ограничение на поставщиков (вам нужно использовать не менее x от общего числа вендоров). Это означает, что вам нужно выбрать по крайней мере 1 продукт у каждого поставщика x... И вот пример решения:

Для каждого поставщика в v, сортируйте продукты по цене, тогда у вас будут "v" наборы отсортированных цен. Теперь вы можете выбрать мин этих наборов и отсортировать снова, создавая новый набор продуктов "v", содержащий только самые дешевые.

Теперь, если p <= v, затем выберите первые p элементов, и вы закончите, в противном случае выберите все элементы v и повторите ту же логику, пока не достигнете p.

Ответ 5

Я не работал и не проверял, но, думаю, это может сработать. Попробуйте следующее:

Добавьте еще две колонки под названием "Самая высокая цена" и "Самая низкая цена" в таблицу и создайте для нее данные: они должны иметь самую высокую и самую низкую цену для каждого продукта среди всех поставщиков. Также добавьте еще один столбец под названием "Диапазон", который должен содержать (самая высокая цена - самая низкая цена).

Теперь сделайте это 100 (p) раз:

• Выберите строку с наибольшим диапазоном. Покупайте продукт с наименьшей ценой на эта строка. После покупки отметьте эту ячейку как "купленную" (возможно, установите значение null).
• Пересчитать минимальную цену, диапазон для этой строки (игнорируя ячейки, отмеченные как "купленные" ).