@konstantin_obukhov

Как вычислить оптимальных поставщиков и кол-во для заказа?

Есть условный массив данных с ценами поставщиков и количеством в наличии, первый элемент в prices массиве это priceBreak где ключ это минимальное кол-во для заказа, а значение это цена за шутку.
Нужен алгоритм или подсказка как лучше его реализовать для поиска оптимальных поставщиков и оптимального кол-ва для закаказа у отдельно взятого по запрошенному кол-ву

$priceLists = [
        [
            'id' => 3,
            'stock' => 10000,
            'prices' => [
                10 => 40,
                25 => 30,
                50 => 20
            ]
        ],
        [
            'id' => 4,
            'stock' => 12000,
            'prices' => [
                1 => 51,
                10 => 41,
                25 => 31,
                50 => 19
            ]
        ],
        [
            'id' => 6,
            'stock' => 2000,
            'prices' => [
                1 => 51,
                10 => 39,
                25 => 29,
                50 => 18
            ]
        ],
        [
            'id' => 9,
            'stock' => 70,
            'prices' => [
                5 => 50,
                10 => 38,
                25 => 28,
                50 => 16
            ]
        ]
    ];


$requestedQuantity = 40;


/** 
 * @return array
*/
function getBestPricesQuantity($priceLists,  $requestedQuantity) {

}


Ожидаю для получения усеченный, модифицированный массив с новым ключом quantity в каждом элементе
  • Вопрос задан
  • 234 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Я придумал решение через динамическое программирование.

Предположение - цены у каждого поставщика не возрастают при увеличении количества заказов. В противном случае, это бред какой-то, а не поставщики.

Ключевое наблюдение - если есть какой-то ответ (распределение заказов по поставщикам), то среди всех активных поставщиков всегда есть кто-то один, у которого текущая цена минимальна. Можно скидывать ему товары от остальных, пока не упремся в границу переключения цены у них. При этом цена у этого поставщика может еще и улучшиться. Общая сумма только улучшиться от этого. Если упремся в запасы этого поставщика, то можно его исключить из рассмотрения и повторить операцию. Таким образом, лишь улучшая ответ, мы придем к тому, что какие-то поставщики продают весь свой запас целиком, какой-то один продает сколько-то (и его цена меньше всех оставщихся). Все оставшиеся продают ровно минимальное количество для какой-то цены (ключ из входных данных). Можно в массив цен у каждого поставщика дописать вариант => <последняя цена>, если там такой записи еще нет. И еще запишите туда 0 => 0 в начало (купить 0 за 0). Тогда все еще упрощается - все поставщики, кроме одного, продают ровно какой-то свой priceBreak штук.

Это простое рассуждение говорит нам, что искать оптимальный ответ можно только среди вот этих вот описанных выше. Потому что любой вариант можно свести к такому, возможно даже улучшив его.

Это уже можно свести к чему-то вроде задачи о рюкзаке. Переберите одного особого поставщика (который будет продавать не фиксированное количество штук). Исключите его из массива поставщиков (но запомните его цены, чтобы считать, сколько ему придется заплатить за остаток).

Теперь, как в задаче о рюкзаке, считайте динамическое програмимрование DP(i,j) - какая минимальная цена, чтобы набрать ровно i штук у первых j заказчиков (и каждый продает ровно какой-то свой priceBreak).

База тривиальна: DP(0,0) = 0, DP(i>0, 0) = infinity (на практике - большое число, или -1 и это значение надо отдельно проверять при переходе).

Переход:
DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

Тут мы просто перебираем, сколько продает последний поставщик. Берем оставшиеся у предыдущих (DP(...,j-1) и прибавляем, сколько заплатим последнему.

Вот, подсчитали вы ДП. Теперь ответ - min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Перебирайте, сколько вы купите у особого поставщика. Берите оставшееся из динамического программирования.

Если поставщиков M, надо купть N штук, у каждого поставщика по K цен, но это решение будет O(M*(M*N*K + N)) по времени и O(M*N) по памяти. (На самом деле, можно уточнить оценку по времени- O(M*(M*N+N*L+N)), где L - общее количество записей в массивах цен у всех поставщиков).

Для восстановления ответа вместе с DP() запоминайте, какое значение k выдало лучший результат. Потом можно будет с конца размотать оптимальный ответ, выдавая известное значение последнему поставщику.

Если цены у поставщиков могут возрастать при увеличении количества, то решение остается в силе, только надо дописать в каждый массив "количество=>цена" элементы с количеством на 1 меньше каждого priceBreak. Потому что теперь в любом ответе все-равно можно будет перекидывать от одного заказчика к другому, пока не упремя или в priceBreak сверху, или в последнее количество с неменяемой ценой. И опять получается, что только один поставщик будет продавать не фиксированное в массиве значение.

Можно вместо ДП гнать симплекс метод, как Philipp уже написал (будет быстрее, если поставщиков мало, а количесто штук очень большое).

Возможно, можно ускорить решение в M раз, если вместо M разных ДП гнать одно со всеми поставщиками. Потом перебрать i<=n, распределить i штук по поставщикам беря только priceBreak, а потом прибавить остаток к поставщику с минимальной ценой (не переваливая за следующий priceBreak!). Но я не уверен, что это будет работать (не смог пока доказать, что, если у оптимального ответа урезать торчащий от priceBreak хвост у кого-то поставщика, то ответ останется оптимальным для нового количества).
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
zoonman
@zoonman
⋆⋆⋆⋆⋆
У вас типичная задача на симплекс-метод.
В данном случае на поиск минимума функции.

https://github.com/uestla/Simplex-Calculator
Ответ написан
Комментировать
SilenceOfWinter
@SilenceOfWinter
та еще зажигалка...
реализация зависит от языка, в общих чертах обходим товары циклом, во вложенном цикле находим мин.стоимость
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы