找到最大有效组合数的算法？
好吧……所以我有一点棘手（至少对我来说）。
我有一个简单对象的列表，我需要弄清楚如何找到使用最大数量的组合。这些对象的类中的每一个都有一个用于其名称的属性（字符串）、一个用于它们想要绑定的其他元素名称的属性（列表），以及一个用于它们与之绑定的其他元素名称的属性（列表）不喜欢粘合。
如果将一个元素添加到集合中，其中该特定元素“喜欢”集合中已有的一个（或多个）其他元素，则添加的元素会为其喜欢的集合中的每一项返回 +1 的分数。同样，对于添加的元素不喜欢的集合中的每个其他元素，都会返回 -1 的分数。将所有元素添加到最终集合后，每个元素的分数必须 >= 0。
我如何找到可以使用的元素组合以返回最大集合？如果多个组合返回相同数量的元素，则应返回所有可能的组合。
我希望这是有道理的...另外，我使用的是 C# (.NET 4.0)，但可以使用任何编程语言，我只需要弄清楚它背后的逻辑。
预先感谢，
桑尼
OK... so I have a bit of a tricky one (for me, at least).
I have a list of simple objects and I need to figure out how to find a combination that makes use of the maximum number. Each of these objects' classes have a property (string) for their name, a property (List) for the other elements' names with which they like to bond, and a property (List) for the other elements' names with which they do not like to bond.
If an element is added to a collection where that specific element "likes" one (or more) of the other elements already in the collection then the added element returns a score of +1 for each item in the collection that it likes. Likewise, a score of -1 is returned for each other element in the collection the added element does not like. After adding all the elements to the final collection, the score for each must be >= 0.
How would I go about find the combination(s) of elements I can use that will return the largest collection? In the event of multiple combinations returning an equal number of elements, all possible combinations should be returned.
I hope that made sense... Also, I'm using C# (.NET 4.0) but any programming language can be used, I just need to figure out the logic behind it.
Thanks in advance,
Sonny
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为你说这是一个棘手的问题是正确的。我将对象视为图表中的节点，将喜欢/不喜欢信息视为赋予节点之间的链接权重。忽略“喜欢”字段并赋予所有链接权重 0 或权重 -1。在这种情况下，您的问题是找到最大节点数，使得它们之间的所有链接的权重均为 0，并且没有一个链接的权重为 -1。假设您有一个程序可以有效地完成此操作。
现在看一下问题http://en.wikipedia.org/wiki/Clique_problem，它是一个已知的难题。如果您遇到最大派系问题，请在所有节点之间创建链接。如果两个节点在 max clique 中链接，则权重为 0。如果不存在链接，则权重为 -1。现在运行一个程序来解决你的问题，你就解决了max clique。所以我认为你的问题是 NP 完全的，并且不太可能有一个有效的解决方案。
I think that you are right to say that this is a tricky problem. I think of objects as nodes in a graph and the like/dislike info as giving weights to links between nodes. Ignore the "like" field and give all links weight 0 or weight -1. In this case, your problem is to find the maximum number of nodes, such that all of the links between them have weight 0, and none of them have weight -1. Suppose that you have a program to do this efficiently.
Now look at the problem http://en.wikipedia.org/wiki/Clique_problem, which is a known hard problem. If you have a max clique problem, then create links between all nodes. Where the two nodes were linked in max clique make the weight 0. Where a link did not exist, make the weight -1. Now run a program to solve your problem, and you have solved max clique. So I think your problem is NP-Complete, and there is very unlikely to be an efficient solution to it.