假設人生可粗分為 小學 國中 高中 大學 四階段，每個階段各有五間學校可以選，圖示 如下 小學 國中 高中 大學 ┌──┐ ┌──┐ ┌──┐ ┌──┐ │ 甲 │ │ 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