Shopping cart minimization algorithm

Question

I have a list of products, which consists of list of shops, which sold it.

{
    'Book A': [ShopA, ShopB, ShopC],
    'Book B': [ShopC, ShopD],
    'Movie C': [ShopA, ShopB, ShopD, ShopE],
    ...
}

(Price differs between the shops)

Each shop is also has a shipping cost. It's a "per-order" shipping cost, it doesn't matter how many items are in my cart. And it differs between the shops too.

Ex: if I buy "Book A" from ShopA, "Book B" from ShopC and "Movie C" from ShopA, the resulting price is: Book A price in ShopA + Book B price in ShopC + Movie C price in ShopA + ShopC shipping cost + ShopA shipping cost

If the shipping cost was zero or it was on per-item basis and constant, than I would just sort the offer lists by price+shipping field and fetch the first result from each set.

I need to buy all the items once and find the minimal price and the resulting set.

I'm not very good with optimization algorithms and dynamic programming so I need a solution or just a nod into the right direction.

Answer 1

This problem is NP Hard.
We will show a reduction from the Hitting Set problem.
Hitting Set problem: Given sets S1,S2,...,Sn and a number k: chose set S of size k, such that for every Si there is an element s in S such that s is in Si. [alternative definition: the intersection between each Si and S is not empty].

Reduction:
Given an instance of hitting set, in the form of (S1,...,Sn,k) create an instance of this problem:

All books cost nothing. In order to buy from each store you pay 1. 
The book i is sold by each store denoted in Si, minimal price for this instance is k.

proof:
Hitting Set -> This problem: Assume there is a minimal hitting set in (S1,...,Sn) of size k. Let this hitting set be S. By buying from each store in S, we can buy all our books at cost k, since the books cost nothing [in our construction], and we bought all books, and we paid for the ordering from stores exactly k, thus the total price was k.
This problem -> Hitting set: Assume there is a pricing of k for the problem at the question. Then, from the building of the problem, and since the books cost nothing, we need to buy in k different stores to get all books. Let these stores be S. From the construction of the problem, S is a hitting set for (S1,...,Sn)
Q.E.D.

Conclusion:
Thus, this problem is "not easier then" Hitting Set Problem, and there is no known polynomial solution for this problem, so - your best shot, if you want optimal solution, is probably an exponential one, such as backtracking [Check all possibilities, and return the minimal solution].

Answer 2

With so little items I have a solution. It is dynamic.

We will process every shop iteratively. At every step we store the current best price with which we can cover all subsets of items. In the beginning all of them are infinity in price except for the empty subset which is 0 of price. Note that all subsets are 2^Num_products in count but in your case these are only about 1000.

Now how do we process the next to follow shop: Consider you cover every possible subset of the products with this shop (i mean subset that the shop can actually provide) and all the rest of the products being covered by shops you already observed, thus improving the minimal costs of covering every subset. This step takes 2^Num_products*2^Num_products=4^Num_products, still about a million which is bareable. You do this for every shop and at the end the answer is the cost of covering all the elements. The whole complexity of the proposed solution is 4^Num_products * num_shops which is about 50 million which is good to go.

Note that this is still exponential and this is not surprising. Thank you to amit for his incredible proof of NP hard.

EDIT Adding further explanation of the algorithm in pseudocode:

init:
 cost[subset] = infi
 cost[{}] = 0
for shop in shops
 new_prices = costs.dup()
 for set : subsets
   for covered_set : all_subsets(set)
     price = covered_set == {} ? 0 : delivery[shop]
     remaining = set
     for element : covered_set
       if shop do not sale element
         break for, choose next covered_set
       price += el_price[element]
       remaining.remove(element)
     price += costs[remaining]
     new_prices[set] = min(new_prices[set], price)
 costs = new_prices
return costs[all]

Note that here I use sets as index - this is because I actually use the bitmask representation of the subsets e.g 1101 is a subset containing the 1st, 2nd and the forth element. Thus an iteration of all sets is for (int i = 0; i < (1 << n); i++).

There is also one more thing: if you want to cycle all the subsets of a subset S you can actually do it faster than iterating all the subsets of the initial set and checking whether the subset is subset of S. If S is also represented with bitmask bit_mask this for loop does the job: for(int i = bit_mask; i > 0; i = (i - 1) & bitmask). Using this approach you decrease the complexity of the algorithm to 3^Num_products * num_shops. However, this is a bit harder to understand and you will probably need to write by hand one example to make sure the loop I wrote actually cycles all the subsets of S. About the complexity - just trust me.

EDIT2 Edited the break condition. also let me elaborate on the set remaining and its calculation: as dmzkrsk pointed out the pseudocode mentions removal from the set, but you can actually just assign remaining = set ^ covered_set (again bit operation) in case of using bitmasks to represent the subsets.

Answer 3

I have dealt with this exact problem once. I didn't come up with any other solution than just testing every possible combination of shops but there is an easy way to filter out many of the shops in every product.

1. Calculate the lowest price (shipping cost included) of every product, let's call it best_price.

2. In every product, retain only the shops where price of the shop (without shipping cost) <= best_price (with shipping cost)

3. Test every possible combination of shops for the cheapest.