給定一組人，每對具有價值，我怎麼才能找到總配價最小的配對配置？

最愚蠢，最暴力，最醜陋的解決方案是這樣的：

獲取對所有可能的配置...

groups = people.combination(2).to_a.combination(people.size/2).to_a
...拒絕所有的不止一次包含同一個人的配置。

groups.reject! { |group| group.flatten.uniq.size < people.size }
然後找到最小值的配置。

groups.min_by { |group| group.inject(0) { |pair| value_for(pair) }

有沒有考慮到的是，這裏的分支和一定的解決方案爲Assignment Problem的修改，該工作和人是都人？

難道還有另一個組合問題，它與我提出的更接近嗎？

如何在不炒我的CPU的情況下獲得最佳解決方案？

謝謝！

不好意思，但是如果每個人都有一個價值，那麼找到最低價值的貨幣是微不足道的 - 大概你只需要選擇存儲該價值的結構呢？我猜你的意思是別的。 –

@AndyJones對於模糊我很抱歉。我不是在尋找具有最低價值的貨幣對，我正在尋找超貨對的總價值最低。假設你有十個人，我想找出5對中哪一個可能的配置產生最低的總和。 –

感謝您的支持 - 我可能是唯一一位閱讀過此文的人，但並未立即明白！ –

回答