※ 引述《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？

如果撇開寫程式 這個演算法邏輯上是可work的 只是我覺得演算法要從能不能用程式解決問題的角度去看問題 有錯請指教 謝謝大大分享

謝謝大大特地回文，我覺得可以找到optimal solution，但要多一些步驟，複雜度也會增加，會不會是因為這樣，這個問題就不算是knapsack problem ，所以用這個解法算是無解？https://goo.gl/tJwUsU爬到的討論意思應該是 real number 不一定可以精確地化成 binary形式 所以未必能找到optimal solution就像一樓大大說的 從程式的角度 不 work

我一開始就已經說了 理論上本來就不可能表示所有實數所以我只考慮可以被精確表示的實數

哦哦sorry沒看清楚 那我覺得應該是因為複雜度沒有bounded在O(nw) 所以答案才給not work