algorithm - 如何从大量产品中找到最便宜的组合

Question

我有一张 table

商店

[A][B][C]

产品

[P1][P2][P3][P4]

价格如下所示

[  ][A][B][C]
[P1][6][4][2]
[P2][3][5][7]
[P3][1][9][9]
[P4][8][4][9]

假设用户想尽可能便宜地购买 2 家商店的所有东西，是否只有高效的算法才能做到这一点？

这是旅行购买者问题吗？

Answer 1

假设:

user want to buy all of the things in 2 stores

算法草图:
使用以商店作为列和行的二维查找表。

[x][A]  [B]  [C]  
[A][inf][]   []  
[B][]   [inf][]  
[C][]   []   [inf]

由于您需要选择两个不同商店，因此对角线被初始化为无穷大。
现在填充查找表的右上三角或左下三角。

例如在[A]、[B]位置你选择了A店和B店，所以只能购买这两家店的商品，也就是说你可以贪心(买便宜的)。最后将价格总和存储在查找表中。
具有最低值的条目是您问题的解决方案。此外，您需要检查一家商店的每种产品都比另一家便宜的情况，因此在此草图中，所有产品都将在一家商店购买。

算法的复杂度应该是 O(n²m)，其中 n 是商店的数量，m 是产品的数量。