Ahmad1's blog

Interesting problem: Need Help
By Ahmad1, history, 8 years ago, In English

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?

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

How big can prices be?

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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).

      → Reply