作者FRAXIS (喔喔)
看板Grad-ProbAsk
標題Re: [理工] 97 暨南 演算法
時間Thu Dec 21 16:46:53 2017
※ 引述《ddd23236 (James)》之銘言：
: 請問一下
: 不太懂這題為什麼 the size of each object
: 一定要是整數
: 我的想法是實數還是可以比較大小，
: 只要取floor 再比較即可
: 變成
: c[ i-1, l_ k-w[ i ] _l + v [ i ] ]
: (抱歉打不出floor符號
: http://i.imgur.com/DlVHalJ.jpg
我認真的回一下這一篇，雖然我不知道這是不是出題者想要的答案。
首先要思考什麼叫做輸入是 arbitrary real number，
在 Turing machine 的模型下，就算有無限的記憶體，能夠表示的也只
是 countable set，不可能表示 arbitrary real number，因為實數是
uncountable的。
所以我假設考官想要問的是，對於背包問題，當輸入可以是實數的一個
可數子集時，dynamic programming 可不可以 *work*。
因為 DP 是基於 optimal substructure 的，也就是題解上列的遞迴式，
這遞迴式跟輸入是不是整數沒有關係，所以 DP 是可以找到最佳解的。
但是時間複雜度就不是O(nW)，W 是背包大小，因為輸入不是整數的關係。
所以是 work 還是不 work？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.34.43
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1513846016.A.5D5.html
推 wsp50317: 如果撇開寫程式 這個演算法邏輯上是可work的 只是我覺得 12/21 17:59
→ wsp50317: 演算法要從能不能用程式解決問題的角度去看問題 有錯請 12/21 17:59
→ wsp50317: 指教 謝謝大大分享 12/21 17:59
推 ddd23236: 謝謝大大特地回文，我覺得可以找到optimal solution，但 12/21 19:12
→ ddd23236: 要多一些步驟，複雜度也會增加，會不會是因為這樣，這個 12/21 19:12
→ ddd23236: 問題就不算是knapsack problem ，所以用這個解法算是無 12/21 19:12
→ ddd23236: 解？ 12/21 19:12
→ ddd23236: 爬到的討論意思應該是 real number 不一定可以精確地化 12/21 19:28
→ ddd23236: 成 binary形式 所以未必能找到optimal solution 12/21 19:28
→ ddd23236: 就像一樓大大說的 從程式的角度 不 work 12/21 19:30
→ FRAXIS: 我一開始就已經說了 理論上本來就不可能表示所有實數 12/21 20:27
→ FRAXIS: 所以我只考慮可以被精確表示的實數 12/21 20:28
→ ddd23236: 哦哦sorry沒看清楚 那我覺得應該是因為複雜度沒有bounde 12/21 21:02
→ ddd23236: d在O(nw) 所以答案才給not work 12/21 21:02