PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 人生成就問題

看板Prob_Solve (計算數學 Problem Solving)作者ECZEMA (加油!)時間14年前 (2010/04/21 06:26)推噓2(2推 0噓 3→)

留言5則, 4人參與討論串1/3 (看更多)

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