最小化產品

Question

我給出3組A，B和C，每組有n個元素。這些集合可以包含重複項（如果Set是正確的話，則不確定）。

現在我試圖形成具有n個元素的一組d（說D1至Dn），含3個元素，一個來自A，一個從B和一個從C.

我的目標是每個元素狄找到使Di中元素的乘積之和最小的集合D.

蠻力似乎是一個非常糟糕的主意，因爲即使n> 5，算法的速度變得非常糟糕。任何人都可以提出更好的方法？線性規劃是否適合這個問題？

Answer 1

所以你想要形成兩個二部圖，它們可以創建A-B和B-C元素的匹配，從而使平均產品（a_i * b_j * c_k）最小化。

不幸的是我相信這是一個NP難題。 （如果你把匹配數的n個3的數量=作爲變量）

我不認爲這兩個匹配數可需單獨製成：

考慮A = {1，10}，B = {1， 10}

A的匹配，B在隔離爲1×10 = 10和1×10 = 10（總共20個）

然而考慮C = {1，10000}

如果我們將A，B與C進行貪婪匹配，我們得到10 x 1 = 10和10 x 10000 = 100000（總計100010）

然而，如果我們有采取的非最佳匹配A的，B爲1×1 = 1和10×10 = 100（總共101）

然後我們可以使用C匹配它爲1 x 10000 = 10000和100 x 10 = 1000（總共11000）

所以我們可以看到有必要考慮所有可能的組合。

這不是證明它是NP難的，但我希望它傳達一種直覺。