Search for the cheapest combination of items with selection conditions

Question

Let's say that I have 3 sellers of a certain subject. Each seller has different quantities of these items. Another product also has a different price.

  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 extra costs per unit . Say, for example, that if I do not order at least 4 units, I will have to pay an additional $ 5 for each ordered unit.

Some examples:

If I wanted to buy 4 units, the best price would come from receiving them from Supplier No. 1 and Supplier No. 2 , instead of receiving everything from Supplier No. 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 the first cheaper ones and the rest from more expensive suppliers

 (17+5)*1 + (18+5)*3 + (23+5)*1 = 119 23 *5 = 115$ <--- Cheaper 

Question

Remembering all this ... If I knew in advance how many items I want to order, what would be the algorithm to find out which of the best combinations I can choose?

Answer 1

As noted in the comments , for this you can use the graph search algorithm, for example the Dijkstra algorithm . It is also possible to use A * , but for this you need a good heuristic function. Using the lowest price may work, but for now, let me stick with Dijkstra's.

One node in the graph is represented as a set (cost, num, counts) , where cost is the cost, obviously, num total number of items purchased and counts breakdown of the number of goods per seller. If cost is the first item in the tuple, the item with the lowest cost will always be at the beginning of the heap . We can process the “extra charge” by adding a fee if the current account for this seller is below the minimum and deducts it again once we reach this minimum.

Here is 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 generator function, i.e. you can use next(find_best(...)) to find only the best combination or next(find_best(...)) over all 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 is 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: Although the above example is suitable for the example, there may be times when it fails, since subtracting the extra cost after reaching the minimum number means that we can have faces with a negative value, which can be a problem in Dijkstra. In addition, we can add all four elements at once to one action. To do this, replace the inside of the algorithm as follows:

  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: In addition, since the order in which items are added to the “path” does not matter, we can limit sellers to those that are not in front of the current seller. We can add a cycle for seller, count in counts: to it:

  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 these two improvements, the state in the graph under study looks like next(find_best(5, 4, 5, price, items)) (click to enlarge):

Note that there are many states “below” the state of the target, and the costs are much worse. This is because these are all states that have been added to the queue, and for each of these states the state of the predecessor is still better than the best state, therefore they were expanded and added, but they never jumped out of the queue. Many of them can probably be trimmed using A * with a heuristic function such as items_left * min_price .

Answer 2

This is a Bounded Knapsack issue. Where do you want to optimize (minimize) the cost with price and quantity restrictions.

Read about 0-1 KnapSack here . If you have only 1 quantity for this supplier.

Read how to extend the 0-1 KnapSack problem for a given value (called Bounded Knapsack ) here

A more detailed discussion of Bounded Knapsack here

This will be enough to come up with an algorithm that requires a bit of tweaking (for example, adding $ 5 when the amount is below some given value)