[問題] 人生成就問題
假設人生可粗分為 小學 國中 高中 大學 四階段，每個階段各有五間學校可以選，圖示
如下
小學 國中 高中 大學
┌──┐ ┌──┐ ┌──┐ ┌──┐
│ 甲 │ │ A │ │ 1 │ │ Ⅰ │
│ │ │ │ │ │ │ │
│ 乙 │ │ B │ │ 2 │ │ Ⅱ │
│ │ │ │ │ │ │ │
│ 丙 │ │ C │ │ 3 │ │ Ⅲ │
│ │ │ │ │ │ │ │
│ 丁 │ │ D │ │ 4 │ │ Ⅳ │
│ │ │ │ │ │ │ │
│ 戊 │ │ E │ │ 5 │ │ Ⅴ │
└──┘ └──┘ └──┘ └──┘
沒有升學門檻，可以從任何小學到任何中學，同理任何中學到高中，任何高中到大學，
也就是說有 5^4 種升學管道，(沒有同級轉學的)
每種升學管道，從小學到大學，可以人生成就分數(滿分 100)來表示，舉例來說：
甲-D-2-Ⅳ 有 80 戊-A-4-Ⅲ 為 15，且提供該張人生成就分數表格可對照。
如果要知道 5 個不是同學的人(也就是任何兩個人不能讀過相同的國小，不能相同國中
，不能相同高中，不能相同大學)
人生成就分數總合最高的 5 條管道，要用什麼演算法比較適合解呢? 這種問題有正確解
嗎? 還是只有近似解?
如果只考慮到高中階段? 是否仍有正確解? 或是再多延伸考慮研究所階段? 是否仍有正
確解? 都可以使用同一個演算法嗎?
(我知道如果只考慮小學 國中，是 bipartite matching 或說是 指派問題，因為沒有
提供兩個階段的人生成就分數，不能用 bipartite matching 兩階段兩階段串聯來解，
人生成就分數只有四個階段一起考慮才有)
若各階段學校數目為 1000 所時，還能用嗎? 告訴我可以參考哪一種演算法就好了…
給我幾個明確的關鍵字…謝謝大家… 希望聽到 「這不就是典型的 _____ 問題嗎？」
XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 213.217.58.18
推
04/21 06:44, , 1F
04/21 06:44, 1F
推
04/21 08:51, , 2F
04/21 08:51, 2F
→
04/21 09:08, , 3F
04/21 09:08, 3F
→
04/21 09:19, , 4F
04/21 09:19, 4F
→
08/22 04:57,
4年前
, 5F
08/22 04:57, 5F
討論串 (同標題文章)