Re: [理工] 97 暨南 演算法
※ 引述《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
推
12/21 17:59,
8年前
, 1F
12/21 17:59, 1F
→
12/21 17:59,
8年前
, 2F
12/21 17:59, 2F
→
12/21 17:59,
8年前
, 3F
12/21 17:59, 3F
推
12/21 19:12,
8年前
, 4F
12/21 19:12, 4F
→
12/21 19:12,
8年前
, 5F
12/21 19:12, 5F
→
12/21 19:12,
8年前
, 6F
12/21 19:12, 6F
→
12/21 19:12,
8年前
, 7F
12/21 19:12, 7F
推
12/21 19:25,
8年前
, 8F
12/21 19:25, 8F
→
12/21 19:28,
8年前
, 9F
12/21 19:28, 9F
→
12/21 19:28,
8年前
, 10F
12/21 19:28, 10F
→
12/21 19:30,
8年前
, 11F
12/21 19:30, 11F
→
12/21 20:27,
8年前
, 12F
12/21 20:27, 12F
→
12/21 20:28,
8年前
, 13F
12/21 20:28, 13F
→
12/21 21:02,
8年前
, 14F
12/21 21:02, 14F
→
12/21 21:02,
8年前
, 15F
12/21 21:02, 15F
討論串 (同標題文章)
