I am given with a certain table
Stores
[A][B][C]
Products
[P1][P2][P3][P4]
And their prices are listed as below
[ ][A][B][C]
[P1][6][4][2]
[P2][3][5][7]
[P3][1][9][9]
[P4][8][4][9]
Assume the user want to buy all of the things in 2 stores as cheap as possible, is there only efficient algorithm for that?
Is this the Travelling Purchaser Problem?
Assuming that:
user want to buy all of the things in 2 stores
Algorithm sketch:
Use a two dimensional lookup tables with stores as columns and rows.
[x][A] [B] [C]
[A][inf][] []
[B][] [inf][]
[C][] [] [inf]
The diagonal is initialized to infinity as you need to select two different stores.
Now fill the upper right triangle or the lower left triangle of the lookup table.
e.g. in position [A],[B] you have selected store A and store B. Therefore it is only possible to buy the products from these two stores, which means you can do a greedy approach (take the cheaper one). Finally store the sum of the prices in the lookup table.
The entry with the lowest value is the solution to your problem.
Furthermore you need to check the case that one store has every product cheaper than the other, so in this sketch all products would be bought in one store.
The complexity of the algorithm should be O(n²m) where n is the number of stores and m is the number of products.