這個問題NP-hard？

我想爲這個問題想出一個合理的算法：這個問題NP-hard？

假設你有一堆球。每個球至少有一種顏色，但也可以是多彩的。每個球上還有一個數字。還有一堆只有一種顏色的盒子。我們的目標是最大限度地提高盒中的球數的總和，唯一的規則是：

，以便放置一個球在一個盒子裏，它必須至少有框的顏色
您只能在每個框中放置一個球。

例如，您可以將藍色和綠色的球放入藍色框或綠色框中，但不能放入紅色框中。

我已經想出了一些優化，在運行時間方面有很大幫助。例如，您可以按照點值的降序排列球。然後，當你從最高到最低，如果球只有一種顏色，並且沒有其他高點球含有這種顏色，你可以把它放在那個盒子裏（並且因此從那個盒子中移除那個盒子和那個球）其餘組合）。

我只是好奇是否有這種類型的問題的動態算法，或者如果它只是旅行推銷員問題的僞裝。如果我知道最多隻有X種顏色，會有幫助嗎？任何幫助是極大的讚賞。謝謝！

編輯 - 這裏有一個簡單的例子：

球：

1紅球 - 5分
1個藍色球 - 3分
1綠/紅球 - 2分
1綠色/藍色球 - 4分
1紅/藍色球 - 1點

盒：

1紅
1藍
1綠色

最優解：

紅球在紅色框
藍色球在藍色框
綠色/藍色球在綠色框

總價值：12分（5 + 3 + 4）

來源

2010-10-03 Kenny

由於所有的球都有一個盒子，所有的組織都有相同的分值，對吧？或者我錯過了什麼？ – TaslemGuy 2010-10-03 00:03:33

您能否詳細說明「最大限度地提高箱子中所有人數的總和」。你想最大化一個盒子嗎？你總是使用所有可用的球嗎？ – JoshD 2010-10-03 00:04:30

你想要優化什麼？特定框中的值總和？所有盒子上的數值總和？ – liori 2010-10-03 00:04:51

這是一種特殊情況maximum weight matching problem on a weighted bipartite graph。構建一個圖形，其左頂點對應於球，其右頂點對應於框，並且邊連接球和具有重量V的框，其中V是如果球可以放置在框中的球上的數字，否則爲0 。添加額外的箱子或球，加入到另一邊的重量爲零的邊緣，直到每邊有相同數量的頂點。您正在查找的作業由結果圖中最大（總）權重匹配中非零權重的邊集確定。

使用Hungarian algorithm可以在O（n^3）時間內解決賦值算法，其中n是球或盒的數量的最大值。（順便說一下，我應該聲明我只提到匈牙利算法，因爲它是我熟悉的理論結果，它大概回答了原始問題是NP難題的標題中的問題，我不知道無論它是在實踐中使用的最佳算法。）

來源

2010-10-03 00:27:15

另一個鏈接：http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs – sdcvvc 2010-10-03 00:29:30

哇，這看起來很有希望！我需要一些時間來消化這個，並且實際嘗試實現它，但是非常感謝你！ – Kenny 2010-10-03 00:39:14

讓我試着更進一步......讓我們說第一個目標是最大限度地放置在盒子裏的球的數量，然後打破平局將是最大的總和。這仍然可以在多項式時間內解決嗎？ – Kenny 2010-10-03 01:01:30

你試過了一個貪婪的alg嗎？按點/數值排序，如果可能的話放在箱子裏。如果有任何異常即時消息id想要看到它們。

來源

2010-10-03 00:29:04 Anders

假設你有一個價值10分的紅色/綠色球和5分的紅色球。你有一個綠色的盒子和一個紅色的盒子。使用貪婪的算法，你首先把紅色/綠色的球放在紅色的盒子裏，然後你不能把紅色的球放在任何地方:( – Kenny 2010-10-03 00:44:15

是的，但我相信你的錯誤。當使用貪婪alg時，您可以將紅色/綠色球放在綠色框中，當有更多選項取決於您時，如何選擇處理它。貪心只希望你在放置5分球之前放置10分球。 – Anders 2010-10-03 13:10:02

如果您必須考慮將來要做的動作，那麼需要大量的額外工作，而貪婪算法以其效率而聞名。貪婪算法是高效的，因爲它們像變革一樣，能夠完全忽略未來，做出任何選擇，從而在本回閤中獲得最高的回報。 – Olathe 2010-10-03 22:35:52

這個問題NP-hard？

回答

相關問題