我想解决的问题是:
我已经向供应商发送了一份产品列表,每个供应商都返回了他们的价格列表。在此基础上,我需要计算出在哪里购买每件商品,记住供应商的运费是一次性的。这意味着,如果我们从他们那里购买的唯一商品是最便宜的供应商,那么去他们那里并不总是划算的。
我已经研究了线性规划来解决这个问题,但它似乎依赖于定价是恒定的这一事实。如果有任何建议,我们将非常感谢。
发布于 2020-04-11 04:32:14
我们可以使用dynamic programming方法来解决这个问题。
让我们将其分解为子问题,其中每个子问题的解决方案是通过p从供应商0通过s购买产品0的成本,以及要从其购买的供应商列表。下面是算法:
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)
https://stackoverflow.com/questions/61147199
复制相似问题