Hello there Stackoverflow people,
I run a site that finds its users the cheapest place to buy books. This is easy for a single book, but for multiple books it can sometimes be cheaper to purchase one book at one store and another book from another store.
Currently I find the cheapest store that sells all books in the user's list, but I want to have a smarter system. Here's some more info:
- The price of a book is constant for a store.
- The price of shipping can vary, depending on # of books or the total value of the books.
- Each shop object can take an array of books and return the shipping cost.
- Frequently, not every shop sells every book.
Not sure if it's cool to link to my site here, but it is listed in my user profile.
I would like to be able to find the cheapest combination of stores and books.
I fear it requires a brute force approach - and with 35 shops, the number of combinations will be enormous for a modest number of books. I have a feeling the number of combination is (#shops)^(#books) - but not 100%
The question is, what approach should I use? Does this problem fit in a well known class of problems? If brute force is required, what's a good way of doing this in Ruby and can I prioritise shops to try first?