正如在
评论中提到的，您可以使用图搜索算法来解决此问题，例如
Dijkstra算法。也可能可以使用
A*，但是要这样做，您需要一个良好的启发式函数。使用最低价格可能有效，但现在让我们坚持使用Dijkstra算法。
图中的一个节点表示为(cost,num,counts)的元组，其中cost显然是成本，num是购买的物品总数，而counts是每个卖家的物品数量。由于cost是元组中的第一个元素，因此具有最低成本的物品将始终位于heap的前面。我们可以通过在当前计数低于最小值的情况下添加费用，并在到达该最小值后再次减去费用来处理“额外费用”。
以下是Python中的简单实现。
import heapq
def find_best(goal, num_cheap, pay_extra, price, items):
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
visited.add((cost, num, counts))
if num == goal:
yield (cost, num, counts)
for seller, count in counts:
if count < items[seller]:
new_cost = cost + price[seller]
if count + 1 < num_cheap: new_cost += pay_extra
if count + 1 == num_cheap: new_cost -= (num_cheap - 1) * pay_extra
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))
上面是一个生成器函数，也就是说，你可以使用
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：虽然上述示例中的方法是有效的，但有时它可能会失败，因为在达到最小数量后减去额外成本意味着我们可能会得到带有负成本的边，这可能在迪杰斯特拉算法中会出现问题。作为替代方案，我们可以在一个“操作”中一次性添加所有四个元素。为此，请使用以下算法替换其内部部分：
if count < items[seller]:
def buy(n, extra):
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)
if count < num_cheap - 1:
buy(1, pay_extra)
if count >= num_cheap:
buy(1, 0)
更新2：另外，由于添加到“路径”中的项目的顺序并不重要，因此我们可以将卖家限制为不在当前卖家之前的那些。我们可以将
for seller, count in counts: 循环添加到他的循环中。
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))（点击放大）：
请注意，目标状态下面有许多状态，其成本要差得多。这是因为这些状态都已添加到队列中，对于这些状态，前任状态仍然比我们的最佳状态更好，因此它们被扩展并添加到队列中，但从未从队列中弹出。通过使用像items_left * min_price这样的启发式函数进行A*搜索，可以消除其中许多状态。
