Re: [問題] 人生成就問題
看板Prob_Solve (計算數學 Problem Solving)作者yoco315 (眠月)時間14年前 (2010/04/22 01:38)推噓3(3推 0噓 1→)留言4則, 4人參與討論串3/3 (看更多)
※ 引述《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
推
04/22 07:47, , 1F
04/22 07:47, 1F
推
04/22 10:06, , 2F
04/22 10:06, 2F
推
04/22 20:53, , 3F
04/22 20:53, 3F
→
04/24 13:42, , 4F
04/24 13:42, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
