algorithm - 最小化产品

Question

我有 3 个集合 A、B 和 C，每个集合有 n 个元素。这些集合可以包含重复项（不确定 Set 是否正确）。

现在我试图用 n 个元素（比如 D1 到 Dn）形成一个集合 D，每个元素 Di 包含 3 个元素，一个来自 A，一个来自 B，一个来自 C。

我的目标是找到最小化 Di 中元素乘积之和的集合 D。

蛮力在这里似乎是一个非常糟糕的主意，因为即使对于 n>5，算法的速度也会非常慢。任何人都可以提出更好的方法吗？线性规划适合这个问题吗？

Answer 1

因此，您想形成两个二分图，创建 AB 和 BC 的元素匹配，从而最小化平均乘积 (a_i * b_j * c_k)。

不幸的是，我相信这是一个 NP 难题。（如果您将匹配数 n=3 作为变量）

我不认为这两个匹配可以单独进行：

考虑 A = {1, 10}，B = {1, 10}

A、B 的匹配是 1 x 10 = 10 和 1 x 10 = 10（总共 20）

但是考虑 C = { 1, 10000 }

如果我们将 A、B 与 C 进行贪心匹配，我们得到 10 x 1 = 10 和 10 x 10000 = 100000（总共 100010）

但是，如果我们将非最优匹配 A、B 设为 1 x 1 = 1 和 10 x 10 = 100（总共 101）

然后我们可以将它与 C 匹配为 1 x 10000 = 10000 和 100 x 10 = 1000（总共 11000）

所以我们可以看到有必要考虑所有可能的组合。

这并不是证明它是 NP 难的，但我希望它传达一种直觉。