假设人生可粗分为 小学 国中 高中 大学 四阶段，每个阶段各有五间学校可以选，图示 如下 小学 国中 高中 大学 ┌──┐ ┌──┐ ┌──┐ ┌──┐ │ 甲 │ │ 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