时间戳

首页 > 解决方案 > 具有附加约束的最小成本问题

algorithm - 具有附加约束的最小成本问题

问题描述

我试图解决的问题：

我已经向供应商发送了一份产品清单，每个供应商都返回了他们的价格清单。基于此，我需要确定在哪里购买每件商品，记住供应商的运费是一次性的。这意味着，如果这是我们从他们那里购买的唯一商品，那么去找最便宜的供应商并不总是具有成本效益。

我已经研究过线性规划来解决这个问题，但它似乎依赖于定价不变的事实。任何指针将不胜感激。

标签： algorithm

解决方案

我们可以使用动态规划方法来解决这个问题。

让我们将其分解为子问题，其中每个子问题的解决方案是从供应商处购买产品的(p, s)成本，以及要购买的供应商列表。这是算法：0p0s

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)

推荐阅读