最大產品在完整的二分圖中完美匹配

Question

我正在嘗試解決此問題：Jobs。 到目前爲止，我認爲問題與Assignment Problem相同，分銷商和地區代表二分圖，邊代表概率。但是在這裏我們需要最大化產品而不是匹配邊權重的總和。

我想到的一個想法是將每個邊權重改爲對數（權重）。然後，問題基本上變成尋找最大總和，然後可以使用Assignment Problem的算法來解決。但是這會帶來一個問題，因爲應用日誌會使邊權重非整數，這是匈牙利算法不適用的。

請建議一些其他的替代方法。

Answer 1

理論上，匈牙利算法在真實權重下正常工作。

實際上，由於大多數整數對數不能完全表示爲浮點數，所以可能會發生舍入會改變最優解。儘管如此，還是有辦法解決這個問題的，但是這個編程競賽問題不太可能需要他們。