寻找最大有效组合数的算法？

我有简单的对象列表，我需要弄清楚如何找到一个组合，使得使用的最大数量。这些对象的每个类都有一个名称属性（字符串），一个属性（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

谢谢，那个维基百科是我试图解释的。我最多只能在十二到十二个节点之间进行处理，所以我想我会试图强制它，看看性能如何。 –

寻找最大有效组合数的算法？

回答

相关问题