[問題] SPOJ 8545:subset sum
看板Prob_Solve (計算數學 Problem Solving)作者KitWoolsey (難得好天氣)時間13年前 (2011/04/14 22:55)推噓4(4推 0噓 16→)留言20則, 7人參與討論串1/1
http://www.spoj.pl/problems/MAIN72/
(題外話: dirty nopaste 是不是壞掉了??)
http://codepad.org/WqDFt07d
我用Python寫的 , 內容大致是 當得知了前t個數的subset sum 後,
再把第t+1個數分別加上前面所有可能的sum,如果有出現未重覆的就加入記錄並加進總和.
時間複雜度應該是O(n^2) (不知道我有沒有搞錯?)
不過還是TLE了 不知道是因為
(1) Python速度太慢?
(2) 我的演算法實際不是n^2?
(3) 這題n^2仍究不夠快@_@?
我對演算法其實還不是很熟@_@ 不知道是哪一種情形 還請板友賜教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.102.225
→
04/14 23:37, , 1F
04/14 23:37, 1F
→
04/15 01:05, , 2F
04/15 01:05, 2F
推
04/15 01:41, , 3F
04/15 01:41, 3F
→
04/15 01:43, , 4F
04/15 01:43, 4F
推
04/15 01:54, , 5F
04/15 01:54, 5F
→
04/15 01:54, , 6F
04/15 01:54, 6F
→
04/15 01:54, , 7F
04/15 01:54, 7F
→
04/15 01:55, , 8F
04/15 01:55, 8F
→
04/15 01:56, , 9F
04/15 01:56, 9F
推
04/15 11:11, , 10F
04/15 11:11, 10F
→
04/15 13:28, , 11F
04/15 13:28, 11F
→
04/15 13:28, , 12F
04/15 13:28, 12F
我跑了n= 10 100 1000的case 看起來是n^2...@@
n= 500 takes 0.212345638688 sec
n=1000 takes 0.843093548846 sec (不過這樣看起來好像太久了.. = = +)
※ 編輯: KitWoolsey 來自: 61.231.96.43 (04/15 23:26)
→
04/15 23:26, , 13F
04/15 23:26, 13F
→
04/15 23:26, , 14F
04/15 23:26, 14F
推
04/15 23:36, , 15F
04/15 23:36, 15F
→
04/15 23:41, , 16F
04/15 23:41, 16F
→
04/15 23:41, , 17F
04/15 23:41, 17F
→
04/16 00:26, , 18F
04/16 00:26, 18F
→
04/16 01:22, , 19F
04/16 01:22, 19F
→
04/16 20:42, , 20F
04/16 20:42, 20F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
