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?