推 yupog2003: 11題我猜題目沒有拍好？ 12/23 22:24
→ yupog2003: 12題，sum要等於m，代表這些integer的range介於1~m 12/23 22:25
→ yupog2003: 用counting sort先排序，需要0(n) 12/23 22:25
→ yupog2003: 然後第一個數先跟最後一個數相加，如果超過m就捨棄最後 12/23 22:29
→ yupog2003: 一個數，然後換第一個數先跟倒數第二個相加，超過m的話 12/23 22:30
→ yupog2003: 再捨棄，一直找到<=m的，等於m的話就找到了，<m的話就 12/23 22:30
→ yupog2003: 第二個數跟剛剛還沒捨棄的倒數第x個數，依此類推 12/23 22:31
→ yupog2003: 阿不對，我想錯了，剛剛那段全部都錯XD 12/23 22:32
→ yupog2003: 12(b)因為m要k=log_2(m)個bit去存他，佔的空間是k 12/23 22:35
→ yupog2003: 所以真正的input size是k，而m=2^k，故O(mn)=O(n*2^k) 12/23 22:36
→ yupog2003: 這個叫做pseudo-polynomial time algorithm 12/23 22:38
→ yupog2003: 這個問題可以叫做weakly-NP-complete 12/23 22:38
→ yupog2003: 12(a)我好像想到了，一樣counting sort 12/23 22:41
→ yupog2003: for i=1 to n 12/23 22:42
→ yupog2003: for j=2 to n 12/23 22:43
→ yupog2003: if a[i]+a[j]>m: 12/23 22:43
→ yupog2003: break; 12/23 22:43
→ yupog2003: 我又打錯了QQ 12/23 22:44
推 gary19941208: 不能用counting sort，題目沒給數字的上限，只說n 12/23 22:48
→ gary19941208: 個數字，這要用DP吧，用m*n的布林矩陣，[m,n]=[m,n- 12/23 22:48
→ gary19941208: 1]or[m-a_n,n-1] 12/23 22:48
→ yupog2003: 阿對吼，所以真的整個想錯了，抱歉 12/23 22:51
→ h9638512: 11題題目真的只有這樣 12/23 23:16
→ yupog2003: 11(a)感覺可以用decision tree，4個數，有4!個leaf 12/23 23:26
→ yupog2003: 樹高為log2(4!)，最少comparison次數為log_2(4!)>4 12/23 23:28
推 Gabino: 11題真的怪 感覺要五次啊？ 12/30 21:37
推 as23041248: 這是不是subset sum problem? 02/08 21:33