CODEWITHSUNDEEP
algorithm
skyegill
skyegill

Reputation: 83

Minimum cost problem with additional constraints

The problem I'm trying to solve:

I've sent a list of products to suppliers, each supplier returns a list of their prices. Based on this I need to work out where to buy each item, bearing in mind that the supplier's shipping cost is a one off. Meaning that it's not always cost effective to go to the cheapest supplier if that's the only item we're buying from them.

I've looked into Linear Programming to solve this but it seems to rely on the fact that pricing is constant. Any pointers would be greatly appreciated.

Upvotes: 3

Views: 193

Answers (1)

Meredith
Meredith

Reputation: 911

We can use the dynamic programming approach to solve this problem.

Let's break this down into subproblems, where the solution to each subproblem (p, s) is the cost of buying products 0 through p from suppliers 0 through s, along with the list of suppliers to buy from. Here is the algorithm:

memo = {}
# example memo entry: memo[3, 4] = 50, [a, b, c] means the 3 products cost 50, and the first is bought
# at supplier number a, the second at b, etc (out of 4 possible suppliers)

for s in range(0, len(suppliers)):
    for p in range(0, len(products)):
        # first we have some base cases
        if p == 0 and s == 0:
             # one product, one supplier
             memo[p, s] = cost(suppliers[s], products[p]), [s]
        elif p == 0:
             # one product, from any supplier
             old_cost, old_list = memo[p, s-1]
             new_cost = cost(suppliers[s], products[p]) + shipping(suppliers[s])
             if new_cost < old_cost:
                 memo[p, s] = new_cost, [s]
             else:
                 memo[p, s] = old_cost, old_list
        elif s == 0:
             # multiple products, one supplier
             cost, old_list = memo[p-1, s]
             cost += cost(suppliers[s], products[p])
             memo[p, s] = cost, old_list + [s]
        else:
            # cost of using the first s-1 suppliers for the first p-1 products
            new_cost, new_sublist = memo[p-1, s-1]
            # add the cost of buying current product (p) at current supplier (s)
            new_cost += cost(suppliers[s], products[p])
            # calculate new shipping costs as well
            if s not in new_sublist:
                # s is a new supplier that we weren't using before, so add shipping
                new_cost += shipping(suppliers[s])
            # add new supplier to list
            new_sublist += [s]
            # now calculate other option, where we don't use this supplier for this product
            old_cost, old_sublist = memo[p, s-1]
            if new_cost < old_cost:
                result = new_cost, new_sublist
            else:
                result = old_cost, old_sublist
            memo[p, s] = result

The final result is memo[P, S] (where S is the number of suppliers and P is the number of product types). The runtime of this algorithm is O(S*P)

Upvotes: 2

Related Questions