貪婪算法以下

我試圖解決使用貪心算法如下問題，貪婪算法以下

我們有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

貪婪算法以下

回答

相關問題