作者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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1513846016.A.5D5.html
1F：推 wsp50317: 如果撇开写程式 这个演算法逻辑上是可work的 只是我觉得 12/21 17:59
2F：→ wsp50317: 演算法要从能不能用程式解决问题的角度去看问题 有错请 12/21 17:59
3F：→ wsp50317: 指教 谢谢大大分享 12/21 17:59
4F：推 ddd23236: 谢谢大大特地回文，我觉得可以找到optimal solution，但 12/21 19:12
5F：→ ddd23236: 要多一些步骤，复杂度也会增加，会不会是因为这样，这个 12/21 19:12
6F：→ ddd23236: 问题就不算是knapsack problem ，所以用这个解法算是无 12/21 19:12
7F：→ ddd23236: 解？ 12/21 19:12
9F：→ ddd23236: 爬到的讨论意思应该是 real number 不一定可以精确地化 12/21 19:28
10F：→ ddd23236: 成 binary形式 所以未必能找到optimal solution 12/21 19:28
11F：→ ddd23236: 就像一楼大大说的 从程式的角度 不 work 12/21 19:30
12F：→ FRAXIS: 我一开始就已经说了 理论上本来就不可能表示所有实数 12/21 20:27
13F：→ FRAXIS: 所以我只考虑可以被精确表示的实数 12/21 20:28
14F：→ ddd23236: 哦哦sorry没看清楚 那我觉得应该是因为复杂度没有bounde 12/21 21:02
15F：→ ddd23236: d在O(nw) 所以答案才给not work 12/21 21:02