看板 [ Grad-ProbAsk ]
討論串[理工] 演算法 0-1knapscak觀念疑問
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#3
Re: [理工] 演算法 0-1knapscak觀念疑問
推噓5(5推 0噓 6→)留言11則，0人參與, 最新作者a19930301 (-手起刀落o`)時間9年前 (2016/11/18 00:00), 9年前編輯資訊
0
0
0
內容預覽:
我認為...背包問題在多項式內 一定 可以解決. 但...在這前提是我仍不知道他的時間為何是長那樣. 以下有些問題想問一下. 看了一下文章都是說O(nW)的W只是個值，我是想成如果W是2000000000... 那麼必然就不是單純一個W可以表示時間. 我的疑問是，之所以要這麼多的時間是因為?. (W
(還有878個字)
#2
Re: [理工] 演算法 0-1knapscak觀念疑問
推噓4(4推 0噓 9→)留言13則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2016/10/09 22:08), 編輯資訊
0
0
0
內容預覽:
要了解這問題，你要知道電腦是怎麼接受輸入的，以 knapsack 問題來說，. 輸入有 n 個物品，第 i 個物品有重量 wi 和價值 vi 。. 除此之外還有一個重量限制 W ，那在電腦之中需要多少 bit 來表示這些輸入？. 假設輸入是下面的形式（當然也可能有其他形式，只是應該不會影響結果）.
(還有603個字)
#1
[理工] 演算法 0-1knapscak觀念疑問
推噓3(3推 0噓 7→)留言10則，0人參與, 最新作者shortid (我是短哀低)時間9年前 (2016/10/09 15:53), 編輯資訊
0
0
0
內容預覽:
大家好. 這裡有一個觀念想要請教各位版友. 書本上說0-1背包問題的複雜度是O(nW)=O(n2^m). m=lg W. 這部分的解釋真的看不太懂，希望可以請教各位. 我的理解是因為W其實僅需lg W bits即可，而卻需要處理W時間，所以相當於輸入m，卻花了2^m等級的時間. 然而如果是這樣我覺得
(還有67個字)
首頁
上一頁
1
下一頁
尾頁