根据选择条件查找最便宜的商品组合 [英] Finding cheapest combination of items with conditions on the selection
问题描述
让我们说我有3个特定商品的卖家。每个卖家都存储了不同数量的商品。
名称 价格 存储单位
供应商＃1 17 $ 1单位
供应商＃2 18 $ 3单位
供应商＃3 23 $ 5单位
如果我没有从同一供应商处订购足够的物品，则必须支付每单位一些额外的费用。例如，假设我不订购至少4个单位，则必须为每个订购单位支付5美元。
一些示例：
如果我要购买4个单位，则最好的价格是从供应商＃1 和供应商＃2 ，而不是从供应商＃3
中获取全部信息（b + b） （17 + 5）* 1 + （18 + 5）* 3 = 91< ---便宜
23 * 4 = 92
但是，如果我要购买5个单位，那么从供应商3 那里获得所有价格，比先从较便宜的供应商那里获得其余价格，而从更昂贵的供应商那里获得其余价格
（17 + 5）* 1 +（18 + 5）* 3 +（23 + 5）* 1 = 119
23 * 5 = 115 $< ---便宜
问题
牢记所有这些...如果我事先知道要订购多少个商品，那将是一个算法找出什么是我可以选择的最佳组合？
如
请注意，在目标状态下方有许多状态，其成本要差得多。这是因为所有这些状态都已添加到队列中，并且对于每个状态，前任状态仍比处于最佳状态更好，因此它们被扩展并添加到队列中，但从未真正从队列中弹出。通过使用具有启发式功能的A *（例如 items_left * min_price ），其中的许多内容可能会被清除。
Lets say that I have 3 sellers of a particular item. Each seller has different amounts of this items stored. The also have a different price for the item.
Name Price Units in storage Supplier #1 17$ 1 Unit Supplier #2 18$ 3 Units Supplier #3 23$ 5 Units
If I do not order enough items from the same supplier, I have to pay some extra costs per unit. Let's say, for example, that if I do not order at least 4 units, I do have to pay extra 5$ for each unit ordered.
Some examples:
If I wanted to buy 4 units, the best price would come from getting them from Supplier #1 and Supplier #2, rather than getting it all from Supplier #3
(17+5)*1 + (18+5)*3 = 91 <--- Cheaper
23 *4 = 92
But if I were to buy 5 units, getting them all from Supplier 3 gives me a better price, than getting first the cheaper ones and the rest from more expensive suppliers
(17+5)*1 + (18+5)*3 + (23+5)*1 = 119
23 *5 = 115$ <--- Cheaper
The question
Keeping all this in mind... If I knew beforehand how many items I want to order, what would be an algorithm to find out what is the best combination I can chose?
As noted in comments, you can use a graph search algorithm for this, like Dijkstra's algorithm. It might also be possible to use A*, but in order to do so, you need a good heuristic function. Using the minimum price might work, but for now, let's stick with Dijkstra's.
One node in the graph is represented as a tuple of (cost, num, counts), where cost is the cost, obviously, num the total number of items purchased, and counts a breakdown of the number of items per seller. With cost being the first element in the tuple, the item with the lowest cost will always be at the front of the heap. We can handle the "extra fee" by adding the fee if the current count for that seller is lower than the minimum, and subtracting it again once we reach that minimum.
Here's a simple implementation in 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
The above is a generator function, i.e. you can either use next(find_best(...)) to find just the best combination, or iterate over all the combinations:
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)
And as we can see, there's an even cheaper solution for buying five items:
(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)))
Update 1: While the above works fine for the example, there can be cases where it fails, since subtracting the extra cost once we reach the minimum number means that we could have edges with negative cost, which can be a problem in Dijkstra's. Alternatively, we can add all four elements at once in a single "action". For this, replace the inner part of the algorithm with this:
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
Update 2: Also, since the order in which the items are added to the "path" does not matter, we can restrict the sellers to those that are not before the current seller. We can add the for seller, count in counts: loop to 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]
With those two improvements, the states in the explored graph looks for next(find_best(5, 4, 5, price, items)) like this (click to enlarge):
Note that there are many states "below" the goal state, with costs much worse. This is because those are all the states that have been added to the queue, and for each of those states, the predecessor state was still better than out best state, thus they were expanded and added to, but never actually popped from the queue. Many of those could probably be trimmed away by using A* with a heuristic function like items_left * min_price.
这篇关于根据选择条件查找最便宜的商品组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
