贪心算法解决以下问题
贪心算法解决以下问题
提问于 2013-04-18 20:40:39
我正在尝试使用贪婪算法来解决以下问题，
我们有n上的朋友，我们想给他们每个人送一份礼物。但是我们不想把同样的礼物送给两个互相认识的人。(如果x知道y，那么y也知道x)。不认识的人可以拿一样的礼物，没问题。我们希望最大限度地减少不同礼物的数量。
这就是我的想法，我们试着让互不相识的人成对，并给他们相同的礼物。但我不确定这是否是贪婪的算法。此外，我们可能想要找到最大的人群，其中没有人认识任何其他人，这样我们就可以给hem相同的礼物。但是我们能做到吗？我们能找到彼此不认识的人的最大组吗？
有人能提出一个贪婪的算法来解决这个问题吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-04-18 20:55:22
您提到的问题是Graph Coloring问题的重述。您必须用颜色标记图的顶点，以使共享同一条边的两个顶点不具有相同的颜色。下面给出的链接指向Greedy Coloring Algorithm。
http://en.wikipedia.org/wiki/Greedy_coloring
Stack Overflow用户
发布于 2013-04-18 20:54:36
这是图着色问题，greedy algorithm for it is straightforward
a greedy coloring is a coloring of the vertices of a graph formed by
a greedy algorithm that considers the vertices of the graph in sequence
and assigns each vertex its first available color页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16083251
复制相关文章
相似问题
腾讯云开发者
