聚會的討厭對象 - 拼圖

Table of Contents


假設有1號到100號總共100個人,
每個人都有一些固定討厭的對象。
每個人討厭的人數都不一定,每個人都不討厭自己。

例如12號討厭3個人,18號討厭6個人之類的。
而每個被討厭的人也都一定討厭那個討厭他的人。

(也就是說,在這個題目裡面「討厭」這個關係是對於雙方都成立的。
若3號討厭8號跟16號,那麼8號跟16號討厭的人裡面也一定有包括3號。
若a討厭b.則b也一定討厭a)

我不屬於這100個人裡面,我知道所有人他們所討厭的人的名單。
現在我的目標是要邀請到最多人數的人來參加聚會。
邀請的對象是誰不重要,重點是「邀請到最多人數,這些人彼此都不討厭對方」。

有什麼好方法可以簡單找到能邀請到最多人數的群體嗎?

--
~帕索板四徵兆~ 戰略高手 遊戲, 數位, 程設
PlayingGame 遊戲 Σ遊戲 棋藝 橋牌
謎  ○ * \○/ (○ Puzzle 益智 ◎
╦╦└□ " ○□═ □  □>
║║√√ ╦══╦ ∥  |\ 歡樂帕索板
上B愛解謎 睡著還惦記 解完好開心 卡解傷腦筋 歡迎你一起來玩ψmaplemiracle

--

All Comments

Necoo avatarNecoo2011-09-16
邀到的人群裡面要有什麼限制好像沒講欸...?
Tristan Cohan avatarTristan Cohan2011-09-17
是不互相討厭嗎?
Freda avatarFreda2011-09-18
這個是計算機科學裡所謂的 maximum independent set problem
Dorothy avatarDorothy2011-09-22
我也重覆看了好幾次....結果發現我看不懂....囧
Gilbert avatarGilbert2011-09-25
如果是的話就是LPH66大說的那樣沒錯XDDD
Gilbert avatarGilbert2011-09-27
所以 L 大 那樣算回答了問題了嗎?
Anthony avatarAnthony2011-09-27
那句話的潛台詞是「這問題目前沒有"有效"解法」...
Tristan Cohan avatarTristan Cohan2011-10-02
以電腦程式(或更廣義叫演算法)來計算的話
所需時間會隨著人數增加而成指數成長
Ida avatarIda2011-10-03
每個人討厭的人的人數不固定 <-- 這句是什麼意思??
Kumar avatarKumar2011-10-06
討厭的人數會變動??
Eden avatarEden2011-10-09
我猜這只是指像某A討厭三個某B討厭四個這種數量不等的情形
Puput avatarPuput2011-10-10
我來改好了....
Eden avatarEden2011-10-12
貪婪法不是n平方?
Sarah avatarSarah2011-10-15
邀請的情況是找100減M.I.S.(找差集合)? MISP是NPC問題阿
Wallis avatarWallis2011-10-18
但還是再找剩下中的MIS直到沒有"討厭"情況存在為止
Vanessa avatarVanessa2011-10-19
所以說最佳解沒有有效解法 找近似解的有效算法比較可行
Jack avatarJack2011-10-22
應該是每個人所討厭人的人數都不一定"相同"