根据选择条件查找最便宜的项目组合
Finding cheapest combination of items with conditions on the selection
假设某件商品有 3 个卖家。每个卖家都存储了不同数量的此类物品。商品的价格也不同。
Name Price Units in storage
Supplier #1 17$ 1 Unit
Supplier #2 18$ 3 Units
Supplier #3 23$ 5 Units
如果我没有从同一个供应商那里订购足够的商品，我必须支付一些额外的费用每件。比方说，如果我没有订购至少 4 个单位，我必须为每个订购单位额外支付 5 美元。
一些例子：
如果我想购买 4 件，最好的价格来自 供应商 #1 和 供应商 #2，而不是全部从 供应商 #3
(17+5)*1 + (18+5)*3 = 91 <--- Cheaper
23 *4 = 92
但是，如果我要购买 5 件，全部从 供应商 3 处购买会比先从更便宜的供应商处购买更便宜的，然后再从更昂贵的供应商处购买其他的价格更好
(17+5)*1 + (18+5)*3 + (23+5)*1 = 119
23 *5 = 115$ <--- Cheaper
问题
记住这一切...如果我事先知道我要订购多少件商品，找出我可以选择的最佳组合的算法是什么？
这是一个 Bounded Knapsack 问题。您想在价格和数量的约束下优化（最小化）成本。
了解 0-1 KnapSack 个问题 here。对于给定的供应商，您只有 1 个数量。
阅读如何扩展给定数量的 0-1 KnapSack 问题（称为 Bounded Knapsack ）here
Bounded KnapSack更详细的讨论是here
这些都足以提出一个需要一些调整的算法（i.g。当数量低于某个给定数量时添加 5 美元）
如 , you can use a graph search algorithm for this, like Dijkstra's algorithm. It might also be possible to use A* 中所述，但为此，您需要一个良好的启发式函数。使用最低价格可能有效，但现在，让我们坚持使用 Dijkstra 的价格。
图中的一个节点表示为(cost, num, counts)的元组，其中cost是成本，显然，num购买的商品总数，counts 每个卖家的商品数量明细。由于 cost 是元组中的第一个元素，成本最低的项目将始终位于 heap 的前面。如果该卖家的当前计数低于最小值，我们可以通过增加费用来处理"extra fee"，并在达到最小值后再次减去它。
这是 Python 中的一个简单实现。
import heapq
def find_best(goal, num_cheap, pay_extra, price, items):
# state is tuple (cost, num, state)
heap = [(0, 0, tuple((seller, 0) for seller in price))]
visited = set()
while heap:
cost, num, counts = heapq.heappop(heap)
if (cost, num, counts) in visited:
continue # already seen this combination
visited.add((cost, num, counts))
if num == goal: # found one!
yield (cost, num, counts)
for seller, count in counts:
if count < items[seller]:
new_cost = cost + price[seller] # increase cost
if count + 1 < num_cheap: new_cost += pay_extra # pay extra :(
if count + 1 == num_cheap: new_cost -= (num_cheap - 1) * pay_extra # discount! :)
new_counts = tuple((s, c + 1 if s == seller else c) for s, c in counts)
heapq.heappush(heap, (new_cost, num+1, new_counts)) # push to heap
以上是一个生成器函数，即您可以使用 next(find_best(...)) 来找到最佳组合，或者遍历所有组合：
price = {1: 17, 2: 18, 3: 23}
items = {1: 1, 2: 3, 3: 5}
for best in find_best(5, 4, 5, price, items):
print(best)
正如我们所见，购买五件商品还有一个更便宜的解决方案：
(114, 5, ((1, 1), (2, 0), (3, 4)))
(115, 5, ((1, 0), (2, 0), (3, 5)))
(115, 5, ((1, 0), (2, 1), (3, 4)))
(119, 5, ((1, 1), (2, 3), (3, 1)))
(124, 5, ((1, 1), (2, 2), (3, 2)))
(125, 5, ((1, 0), (2, 3), (3, 2)))
(129, 5, ((1, 1), (2, 1), (3, 3)))
(130, 5, ((1, 0), (2, 2), (3, 3)))
更新 1：虽然上面的例子很好用，但是 可以 失败的情况，因为一旦我们达到最小数量就减去额外成本意味着我们可以具有 具有负成本的边 ，这在 Dijkstra 中可能是一个问题。或者，我们可以在单个 "action" 中一次添加所有四个元素。为此，将算法的内部部分替换为：
if count < items[seller]:
def buy(n, extra): # inner function to avoid code duplication
new_cost = cost + (price[seller] + extra) * n
new_counts = tuple((s, c + n if s == seller else c) for s, c in counts)
heapq.heappush(heap, (new_cost, num + n, new_counts))
if count == 0 and items[seller] >= num_cheap:
buy(num_cheap, 0) # buy num_cheap in bulk
if count < num_cheap - 1: # do not buy single item \
buy(1, pay_extra) # when just 1 lower than num_cheap!
if count >= num_cheap:
buy(1, 0) # buy with no extra cost
更新 2：此外，由于将商品添加到 "path" 的顺序无关紧要，我们可以将卖家限制为不在当前卖家之前的卖家。我们可以将 for seller, count in counts: 循环添加到 his:
used_sellers = [i for i, (_, c) in enumerate(counts) if c > 0]
min_sellers = used_sellers[0] if used_sellers else 0
for i in range(min_sellers, len(counts)):
seller, count = counts[i]
通过这两项改进，探索图中的状态看起来像这样 next(find_best(5, 4, 5, price, items))（点击放大）：
请注意，有许多状态 "below" 目标状态，成本更差。这是因为这些都是已添加到队列中的状态，并且对于这些状态中的每一个，前导状态仍然比最佳状态更好，因此它们被扩展并添加到队列中，但实际上从未从队列中弹出。通过将 A* 与启发式函数一起使用，例如 items_left * min_price.
，其中许多可能会被修剪掉
假设某件商品有 3 个卖家。每个卖家都存储了不同数量的此类物品。商品的价格也不同。
Name Price Units in storage Supplier #1 17$ 1 Unit Supplier #2 18$ 3 Units Supplier #3 23$ 5 Units
如果我没有从同一个供应商那里订购足够的商品，我必须支付一些额外的费用每件。比方说，如果我没有订购至少 4 个单位，我必须为每个订购单位额外支付 5 美元。
一些例子：
如果我想购买 4 件，最好的价格来自 供应商 #1 和 供应商 #2，而不是全部从 供应商 #3
(17+5)*1 + (18+5)*3 = 91 <--- Cheaper
23 *4 = 92
但是，如果我要购买 5 件，全部从 供应商 3 处购买会比先从更便宜的供应商处购买更便宜的，然后再从更昂贵的供应商处购买其他的价格更好
(17+5)*1 + (18+5)*3 + (23+5)*1 = 119
23 *5 = 115$ <--- Cheaper
问题
记住这一切...如果我事先知道我要订购多少件商品，找出我可以选择的最佳组合的算法是什么？
这是一个 Bounded Knapsack 问题。您想在价格和数量的约束下优化（最小化）成本。
了解 0-1 KnapSack 个问题 here。对于给定的供应商，您只有 1 个数量。
阅读如何扩展给定数量的 0-1 KnapSack 问题（称为 Bounded Knapsack ）here
Bounded KnapSack更详细的讨论是here
这些都足以提出一个需要一些调整的算法（i.g。当数量低于某个给定数量时添加 5 美元）
如
图中的一个节点表示为(cost, num, counts)的元组，其中cost是成本，显然，num购买的商品总数，counts 每个卖家的商品数量明细。由于 cost 是元组中的第一个元素，成本最低的项目将始终位于 heap 的前面。如果该卖家的当前计数低于最小值，我们可以通过增加费用来处理"extra fee"，并在达到最小值后再次减去它。
这是 Python 中的一个简单实现。
import heapq
def find_best(goal, num_cheap, pay_extra, price, items):
# state is tuple (cost, num, state)
heap = [(0, 0, tuple((seller, 0) for seller in price))]
visited = set()
while heap:
cost, num, counts = heapq.heappop(heap)
if (cost, num, counts) in visited:
continue # already seen this combination
visited.add((cost, num, counts))
if num == goal: # found one!
yield (cost, num, counts)
for seller, count in counts:
if count < items[seller]:
new_cost = cost + price[seller] # increase cost
if count + 1 < num_cheap: new_cost += pay_extra # pay extra :(
if count + 1 == num_cheap: new_cost -= (num_cheap - 1) * pay_extra # discount! :)
new_counts = tuple((s, c + 1 if s == seller else c) for s, c in counts)
heapq.heappush(heap, (new_cost, num+1, new_counts)) # push to heap
以上是一个生成器函数，即您可以使用 next(find_best(...)) 来找到最佳组合，或者遍历所有组合：
price = {1: 17, 2: 18, 3: 23}
items = {1: 1, 2: 3, 3: 5}
for best in find_best(5, 4, 5, price, items):
print(best)
正如我们所见，购买五件商品还有一个更便宜的解决方案：
(114, 5, ((1, 1), (2, 0), (3, 4)))
(115, 5, ((1, 0), (2, 0), (3, 5)))
(115, 5, ((1, 0), (2, 1), (3, 4)))
(119, 5, ((1, 1), (2, 3), (3, 1)))
(124, 5, ((1, 1), (2, 2), (3, 2)))
(125, 5, ((1, 0), (2, 3), (3, 2)))
(129, 5, ((1, 1), (2, 1), (3, 3)))
(130, 5, ((1, 0), (2, 2), (3, 3)))
更新 1：虽然上面的例子很好用，但是 可以 失败的情况，因为一旦我们达到最小数量就减去额外成本意味着我们可以具有 具有负成本的边 ，这在 Dijkstra 中可能是一个问题。或者，我们可以在单个 "action" 中一次添加所有四个元素。为此，将算法的内部部分替换为：
if count < items[seller]:
def buy(n, extra): # inner function to avoid code duplication
new_cost = cost + (price[seller] + extra) * n
new_counts = tuple((s, c + n if s == seller else c) for s, c in counts)
heapq.heappush(heap, (new_cost, num + n, new_counts))
if count == 0 and items[seller] >= num_cheap:
buy(num_cheap, 0) # buy num_cheap in bulk
if count < num_cheap - 1: # do not buy single item \
buy(1, pay_extra) # when just 1 lower than num_cheap!
if count >= num_cheap:
buy(1, 0) # buy with no extra cost
更新 2：此外，由于将商品添加到 "path" 的顺序无关紧要，我们可以将卖家限制为不在当前卖家之前的卖家。我们可以将 for seller, count in counts: 循环添加到 his:
used_sellers = [i for i, (_, c) in enumerate(counts) if c > 0]
min_sellers = used_sellers[0] if used_sellers else 0
for i in range(min_sellers, len(counts)):
seller, count = counts[i]
通过这两项改进，探索图中的状态看起来像这样 next(find_best(5, 4, 5, price, items))（点击放大）：
请注意，有许多状态 "below" 目标状态，成本更差。这是因为这些都是已添加到队列中的状态，并且对于这些状态中的每一个，前导状态仍然比最佳状态更好，因此它们被扩展并添加到队列中，但实际上从未从队列中弹出。通过将 A* 与启发式函数一起使用，例如 items_left * min_price.