作者yoco315 (眠月)
站內Prob_Solve
標題Re: [問題] 人生成就問題
時間Thu Apr 22 01:38:01 2010
※ 引述《ECZEMA (加油!)》之銘言：
: 小學 國中 高中 大學
: ┌──┐ ┌──┐ ┌──┐ ┌──┐
: │ 甲 │ │ A │ │ 1 │ │ Ⅰ │
: │ 乙 │ │ B │ │ 2 │ │ Ⅱ │
: └──┘ └──┘ └──┘ └──┘
把問題簡化一下的話，
變成只有兩個人，問「怎麼選兩條路徑，其分數和最高」。
又因為兩人不得為同學，故一個人選某一班，另一個人就得選另外一班，
如果第一個人在某一階段選 0 班，另一個人就必選 1 班。
這問題即可簡化成「一 binary string，其分數由查表得知，求分數最大者」，
至此顯然可知，若分數表無特殊性質，則此問題必為 NP。
解法就是試過所有的 binary string 組合。
如果只有兩班可以選，複雜度為 O(2^(stage-1))。
如果有 n 班可以選，複雜度為 O( n!^(stage-1) )。
如果 stage 如原題限定只有四階、五班，
120 ^ 3 = 1,728,000，其實很小，可解 XD
再多一階的話就是 207,360,000，用力一點跑還是可以啦～
再多一階就 24,883,200,000 了，應該就不會想算了
至於 1000 階的話......
我只能說這個人好可憐，書要唸這麼久.......... XD
--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈. L. Peter Deutsch
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.115.200
1F：推 LPH66:推一個 04/22 07:47
2F：推 linjack:厲害 <(_ _)> 04/22 10:06
3F：推 keeperkai:所以其實最後就只能用暴力法? 04/22 20:53
4F：→ ECZEMA:可是我的是 1000 班 四階… (1000!)^3 也滿慘的~ 04/24 13:42