作者privatewind (傷神客)
看板Grad-ProbAsk
標題[理工] [資結] 96清大資結
時間Mon Mar 8 18:50:07 2010
http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/96/2101.pdf
請問 第3, 5, 6題 答案為何?
第2題 subset-sum,我知道為NP-Complete
在Introduction to Algorithm中, 有一相關練習題
Exercises 34.5-4
Show that the subset-sum problem is solvable in polynomial time if the target
value t is expressed in unary.
只是手邊沒有I2A的解答本, 不知是否有板友可提供?
========================================================
第5題, 我寫 false , false 不知是否與大家一樣?
========================================================
第6題的答案 我是寫T N N N N
a. 這題意思我有點看不懂
b. hash後, 若有碰撞, 則會不一樣
c. 應該是動態 dynamic
d. 我認為是if, 如fibonacci
e. 這個，我不知道怎麼說明
但是答案不確定又不知道該如何說明, 懇請賜教
謝謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 120.107.174.109
推 assassin88:5. FF 03/08 19:23
→ assassin88:6. FTTFF = =" 03/08 19:24
→ privatewind:6的b 我是想當hash後, 若碰撞發生, 好像結果會不同? 03/08 19:26
推 assassin88:打錯 FFFFF 03/08 19:27
→ assassin88:A. 我是覺得array具locality.. 03/08 19:28
※ 編輯: privatewind 來自: 120.107.174.109 (03/08 19:36)
推 FRAXIS:Subset-sum problem是用Dynamic Programming解 03/08 20:11
→ privatewind:請問一下, DP的方法為? 03/08 20:28
推 FRAXIS:Wiki上搜尋Subset-Sum problem就有了.. 03/08 21:56
→ privatewind:應該說 我知道一般的DP方法就是把subset設成兩種情況 03/08 22:40
→ privatewind:一種是1~i有利用到i 另一種情況是1~i-1 不利用第i個 03/08 22:41
→ privatewind:只是我不清楚有沒有什麼方法 可以針對t=O(n^3.5)的 03/08 22:42