Finding cheapest combination of items with conditions on the selection

Question

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?

Answer 1

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.