2

我正在尝试使用贪心算法解决以下问题，

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

这就是我的想法，我们试着让彼此不认识的人成对，给他们同样的礼物。但我不确定这是否是一个贪心算法。此外，我们可能希望找到最多的人，其中没有人知道任何其他人，所以我们可以给他们同样的礼物。但是我们能做到吗？我们能找到最大的不认识的人吗？

任何人都可以为这个问题提出一个贪心算法吗？

4

2 回答 2

1

这是图形着色问题，它的贪心算法很简单：

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-18T12:54:35.647 回答
1

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

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

于 2013-04-18T12:55:22.207 回答