作者KitWoolsey (难得好天气)
看板Prob_Solve
标题[问题] SPOJ 8545:subset sum
时间Thu Apr 14 22:55:38 2011
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
1F：→ tkcn:3 04/14 23:37
2F：→ KitWoolsey:那正解是n or nlgn @@? 可以给点提示吗 04/15 01:05
3F：推 seanwu:是2... n=100的n^2怎麽可能不会过XD 你的做法是 2^n 04/15 01:41
4F：→ seanwu:呃..如果你要说因为数字范围给定<=1000所以是1000n^2也行啦 04/15 01:43
5F：推 seanwu:刚刚传ac了，你的想法是正确的 04/15 01:54
6F：→ seanwu:问题在於python的list(是吗?不太熟)，那个 not in 的操作 04/15 01:54
7F：→ seanwu:不知道它是怎麽做的，不过我想应该不是 O(1) 04/15 01:54
8F：→ seanwu:考虑到数字总和的上限是10^5，直接用一个bit array检查 04/15 01:55
9F：→ seanwu:会快很多。附带一提，我用C写的时间是 0.03 04/15 01:56
10F：推 tkcn:我错了，没仔细看程式跟题目 Orz 04/15 11:11
11F：→ AmosYang: Proving an upper bound is human; an lower bound, 04/15 13:28
12F：→ AmosYang: divine. XD 04/15 13:28
我跑了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)
13F：→ KitWoolsey:还是我就乖乖用C郝了@_@ 04/15 23:26
14F：→ KitWoolsey:n=100 0.008秒左右 还是太慢QQ? 04/15 23:26
15F：推 suhorng:自己测的话说不定会有数值问题 可能测不到比较强的测资 ? 04/15 23:36
16F：→ KitWoolsey:不知道会有什麽比较难的case @_@ 04/15 23:41
17F：→ KitWoolsey:我有点怀疑是我光IO就超时了. @_@ 04/15 23:41
18F：→ bleed1979:输了，我跑0.04s。 04/16 00:26
19F：→ danielsig727:配备不同不能这样比吧@@" 04/16 01:22
20F：→ KitWoolsey:?_? 04/16 20:42