Проблема минимальной стоимости с дополнительными ограничениями

Question

Проблема, которую я пытаюсь решить:

Я отправил список продуктов поставщикам, каждый поставщик возвращает список своих цен. Исходя из этого, мне нужно выяснить, где можно купить каждый товар, учитывая, что стоимость доставки поставщика разовая. Это означает, что не всегда экономически выгодно go для самого дешевого поставщика, если это единственный товар, который мы покупаем у него.

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

Answer 1

Для решения этой проблемы мы можем использовать Dynami c Programming .

Давайте разберем это на подзадачи, где решение каждой подзадачи (p, s) - это стоимость закупка продуктов от 0 до p у поставщиков 0 до s вместе со списком поставщиков для покупки. Вот алгоритм:

memo = {}
# example memo entry: memo[3, 4] = 50, [a, b, c] means the 3 products cost 50, and the first is bought
# at supplier number a, the second at b, etc (out of 4 possible suppliers)

for s in range(0, len(suppliers)):
    for p in range(0, len(products)):
        # first we have some base cases
        if p == 0 and s == 0:
             # one product, one supplier
             memo[p, s] = cost(suppliers[s], products[p]), [s]
        elif p == 0:
             # one product, from any supplier
             old_cost, old_list = memo[p, s-1]
             new_cost = cost(suppliers[s], products[p]) + shipping(suppliers[s])
             if new_cost < old_cost:
                 memo[p, s] = new_cost, [s]
             else:
                 memo[p, s] = old_cost, old_list
        elif s == 0:
             # multiple products, one supplier
             cost, old_list = memo[p-1, s]
             cost += cost(suppliers[s], products[p])
             memo[p, s] = cost, old_list + [s]
        else:
            # cost of using the first s-1 suppliers for the first p-1 products
            new_cost, new_sublist = memo[p-1, s-1]
            # add the cost of buying current product (p) at current supplier (s)
            new_cost += cost(suppliers[s], products[p])
            # calculate new shipping costs as well
            if s not in new_sublist:
                # s is a new supplier that we weren't using before, so add shipping
                new_cost += shipping(suppliers[s])
            # add new supplier to list
            new_sublist += [s]
            # now calculate other option, where we don't use this supplier for this product
            old_cost, old_sublist = memo[p, s-1]
            if new_cost < old_cost:
                result = new_cost, new_sublist
            else:
                result = old_cost, old_sublist
            memo[p, s] = result

Конечный результат - memo[P, S] (где S - количество поставщиков, а P - количество типов продуктов). Время выполнения этого алгоритма O (S * P)