最小成本问题及其他限制条件

Question

最小成本问题及其他限制条件

algorithm

3

我需要解决的问题是：

我已向供应商发送了一份产品清单，每个供应商返回其价格清单。基于此，我需要确定在哪里购买每件物品，考虑到供应商的运输成本是一次性的。也就是说，如果我们只从最便宜的供应商购买该商品，那么并不总是划算的。

我已经研究了线性规划来解决这个问题，但似乎它依赖于定价是恒定的这一事实。如有建议，敬请赐教。

- skyegill

它需要多高效呢？暴力解决方案并不难想出。 - Mitch

这并不难，但肯定非常慢。人们会暴力枚举供应商子集和每个供应商子集中的产品子集。 - Daniel

@Daniel 我会这样做，对于每个项目，你有|供应商|的选择去购买它，尝试每个选项。这将是O（|供应商|^|产品|），但对于足够小的输入来说，在现实世界中可能已经足够好了。 - Mitch

你也可以添加一些剪枝技术来减少代码量。 - Mitch

这里并不清楚你是否需要任何优化。简单的情况（例如运输）可以归结为每个供应商一行，每个产品一列。在没有其他限制条件的情况下，你会从拥有最便宜产品价格（MIN列）的供应商那里购买。你的产品/供应商列表有多大？ - Chris

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Meredith · Accepted Answer

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

让我们将其分解为子问题，其中每个子问题的解（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）。