Hello everyone, I faced this problem at my work, and I was wondering if anyone can help me with it?
A customer has a menu that contains 100 distinct items, and he only knows 6 shops where he can buy these items from.
Let's assume that every shop has all the needed items, and each Item_i has a shipping cost and a price.
Every shop has an offer, which says that if your bill is >= X, you will get a discount by Y%.
We have to help the customer to buy all the required items with the minimal total cost.
Please notice that every shop has its own shipping cost and price for every item, and that discounts only apply on the total bill price (but shipping costs are not included). The total final cost includes the price after the discount and the shipping cost of the chosen items.
I could only come up with a brute force (backtrack) solution that works in 6^100, which is too slow. Can anyone give me an idea to find the optimal solution within a reasonable complexity?
How big can prices be?
About 1000
It's sometimes impossible to find an optimal solution. Let me propose something fast that isn't necessarily optimal.
I assumed that shipping costs should be summed up, since you didn't say otherwise. And there is only one possible discount for each shop, right?
Iterate over 26 possibilities — in which shops we want to use a discount. Now we know exact prices everywhere. Assign products randomly to shops, maybe trying to make it reasonable with some heuristics (but likely it isn't necessary). Apply simulated annealing now: try moving and swapping products between shops so that after some time previously fixed shops have a bill of some size or bigger. You can repeat the process a few times (starting from different initial assignment) and choose the best solution.
Actually the shipping cost for a specific item is different form one shop to another, and each shop has only one discount.
I think your approach is some thing like Genetics Algorithms (which used to find an approximate solution for Travelling Salesman problem), I think it will find a reasonable solution close to the optimal.
Thanks .
I meant: I assumed that it isn't cheaper to order many similar products from the same shop. I wasn't sure about it because usually I pay only once for shipping one type of products (e.g. when ordering books).