我得到了某张桌子
专卖店
[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 家商店的所有东西，是否只有有效的算法呢？
这是旅行购买者问题吗？
3 回答
4
假如说：
用户想购买 2 家商店的所有东西
算法草图：
使用二维查找表，将商店作为列和行。
[x][A] [B] [C]
[A][inf][] []
[B][] [inf][]
[C][] [] [inf]
对角线初始化为无穷大，因为您需要选择两个不同的商店。
现在填充查找表的右上角三角形或左下角三角形。
比如在位置[A],[B]你选择了A店和B店。因此只能从这两家店购买产品，这意味着你可以做一个贪婪的方法（取便宜的那个）。最后将价格总和存储在查找表中。
具有最低值的条目是您的问题的解决方案。此外，您需要检查一家商店的每种产品都比另一家便宜的情况，因此在此草图中，所有产品都将在一家商店购买。
算法的复杂度应该是 O(n²m)，其中 n 是商店的数量，m 是产品的数量。
于 2015-07-24T11:32:14.057 回答
0
我觉得只能使用排除。在每一步，您都会删除一个效率最低的商店。这使得多项式解决方案在最坏的 O(N³) 时间复杂度下。
于 2015-07-24T11:16:00.893 回答
0
您可以再添加三列。
一分钟（A，B）
一分钟（A，C）
一分钟（B，C）
计算这三列的总和。如果最小总和是列 min(A,C)，则转到商店 A 和 C。
该算法在复杂性方面将非常有效。
于 2015-07-24T11:42:06.220 回答