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