尋找最大有效組合數的算法？

我有簡單的對象列表，我需要弄清楚如何找到一個組合，使得使用的最大數量。這些對象的每個類都有一個名稱屬性（字符串），一個屬性（List）用於他們想要綁定的其他元素名稱，還有一個屬性（List）用於其他元素的名稱不喜歡結合。

如果一個元素被添加到集合，其中該特定元素「喜歡」已經在其它元件的集合中的一個（或多個），則添加的元素集合中返回一個得分的1對每個項目，它喜歡。同樣，對於添加元素不喜歡的集合中的每個其他元素，都會返回-1的分數。將所有的元素，最終收集之後，比分爲每個必須> = 0

我怎麼會去尋找元素的組合（S）我可以使用，將返回最大的集？如果多個組合返回相同數量的元素，則應返回所有可能的組合。

我希望是有道理的......另外，我使用C＃（.NET 4.0），但可以使用任何編程語言，我只需要弄清楚一個道理。

由於提前，
桑尼

來源

2011-10-20 Sonny Boy

是否有對象的有限集合，或者你正在尋找對象的具體範圍是多少？一個對象可以在一個集合中重複嗎？ – jball

此外，是否爲每件商品預先確定並固定了「喜歡」和「不喜歡」列表，並且它們對於所有商品的長度是否相同？如果長度不同，您可以嘗試按照流行度對項目進行排序，然後再添加它們。 –

關係是對稱的嗎？我的意思是如果A喜歡B，是否意味着B喜歡A，如果A不喜歡B，是否意味着B不喜歡A？ –

我認爲你是對的，這不能不說是一個棘手的問題。我將對象看作圖中的節點等等/不喜歡將信息賦予節點之間的鏈接權重。忽略「like」字段並給出所有鏈接權重0或權重-1。在這種情況下，您的問題是要找到最大數量的節點，以便它們之間的所有鏈接都具有權重0，並且它們中沒有一個權重爲-1。假設你有一個程序來有效地完成這個任務。

現在看問題http://en.wikipedia.org/wiki/Clique_problem，這是一個已知的難題。如果您有最大集團問題，則在所有節點之間創建鏈接。如果兩個節點在最大團體中鏈接，則權重爲0.如果鏈接不存在，則將權重設爲-1。現在運行一個程序來解決你的問題，你已經解決了最大集團。所以我認爲你的問題是NP-Complete，並且很難有效地解決它。

來源

2011-10-21 04:17:38 mcdowella

謝謝，那個維基百科是我試圖解釋的。我最多隻能在十二到十二個節點之間進行處理，所以我想我會試圖強制它，看看性能如何。 –

尋找最大有效組合數的算法？

回答

相關問題