So I have following problem:
There is k stores and n items. Every store can have these items at different prices (and there are stores that don't have all items). But if you want to buy in a specific store, you must pay one-time fee, which is different for every store. How to find the cheapest way to buy all items?
The only solution I have now is to try every possible combination of shops and look for the cheapest. Is there a better way or some heuristic approximation?
There's a pretty simple reduction of 3-SAT to this problem, so it's NP-hard (introduce a store for each variable and for the complement of each variable, one time fee of 1, then have as the items for a store all clauses satisfied by the variable or complement, as well as a special item for each variable which is sold only in the variable and complement store, all of cost 0, and see if you can buy everything for price k). So there's not going to be a "better way" in the sense of an algorithm which is guaranteed to produce an optimal result with better complexity than a brute-force search.
I think simulated annealing would work well here: In each annealing step either add or remove a store, then find the lowest cost for that store selection.