贪婪算法以下

我试图解决使用贪心算法如下问题，贪婪算法以下

我们有n朋友，我们想送礼物给他们每个人。但我们不想把同样的礼物交给两个相互认识的人。（如果x知道y，那么y知道x）。不认识对方的人可能会拿同样的礼物，没关系。我们希望尽量减少不同礼物的数量。

这是我的想法，我们试着让一对不相识的人给他们所有的同样的礼物。但我不确定这是否是一种贪婪的算法。此外，我们可能想找到最多的人群，其中没有人知道任何其他人，所以我们可以给予同样的礼物。但我们可以这样做吗？我们能找到最多不相识的人吗？

任何人都可以提出一个贪婪算法的问题？

来源

2013-04-18 yrazlik

如上所述，这是一个图着色问题。注 - [“贪婪色彩通常不会使用最少数量的可能颜色”]（http://en.wikipedia.org/wiki/Greedy_coloring）。 – Dukeling

你提到的问题是Graph Coloring问题的重述。您必须用颜色标记图的顶点，使得共享相同边的两个顶点没有相同的颜色。下面给出的链接是Greedy Coloring Algorithm。

http://en.wikipedia.org/wiki/Greedy_coloring

来源

2013-04-18 12:55:22 Deepu

这是图的着色问题，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

来源

2013-04-18 12:54:35 MBo

贪婪算法以下

回答

相关问题