如中所述comments https://stackoverflow.com/questions/42556859/finding-cheapest-combination-of-items-with-conditions-on-the-selection/42575089#comment72248426_42556859，您可以为此使用图搜索算法，例如迪杰斯特拉算法 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm。也可以使用A* https://en.wikipedia.org/wiki/A*_search_algorithm，但为了做到这一点，您需要一个良好的启发式函数。使用最低价格可能可行，但现在我们还是坚持使用 Dijkstra's。
图中的一个节点表示为一个元组(cost, num, counts), where cost显然是成本，num购买的商品总数，以及counts每个卖家的商品数量明细。和cost作为元组中的第一个元素，成本最低的项目将始终位于元组的前面heap。如果该卖家的当前数量低于最小值，我们可以通过添加费用来处理“额外费用”，并在达到该最小值后再次减去该费用。
这是 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：虽然上面的示例工作正常，但是can在失败的情况下，因为一旦我们达到最小数量就减去额外的成本意味着我们可以具有负成本的边，这可能是 Dijkstra 的一个问题。或者，我们可以在一个“操作”中一次性添加所有四个元素。为此，将算法的内部部分替换为：
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：此外，由于将商品添加到“路径”的顺序并不重要，因此我们可以将卖家限制为不在当前卖家之前的卖家。我们可以添加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))像这样（点击放大）：
请注意，有许多状态“低于”目标状态，其成本要差得多。这是因为这些是已添加到队列中的所有状态，并且对于每个状态，前驱状态仍然优于最佳状态，因此它们被扩展并添加到队列中，但从未真正从队列中弹出。其中许多可能可以通过使用带有启发式函数的 A* 来消除，例如items_left * min_price.
