如何从众多产品中找到最便宜的组合

假设:

用户想在2家商店购买所有商品

算法示意图:
使用存储为列和行的二维查找表。

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

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

e、 g.在位置[A],[B],你选择了A店和B店。因此,只能从这两家店购买产品,这意味着你可以采取贪婪的方法(选择更便宜的一家)。最后将价格的总和存储在查找表中。
具有最低值的条目是问题的解决方案。 此外,您需要检查一家商店的每种产品都比另一家便宜的情况,因此在这个草图中,所有产品都将在一家商店购买。

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

我觉得只使用排除是可能的。在每一块牛排上,你都会移除一家最不合适的商店。这使得在最坏的O(N)时间复杂度下求解多项式。

您可以再添加三列。

1分钟(A,B)

1分钟(A,C)

1分钟(B,C)

计算这三个新列的总和。如果最低总和是第min列(A,C),则转到存储A和C。

就复杂性而言,该算法将非常有效。