Re: [理工] 演算法 0-1knapscak觀念疑問
我認為...背包問題在多項式內 一定 可以解決
但...在這前提是我仍不知道他的時間為何是長那樣
以下有些問題想問一下
看了一下文章都是說O(nW)的W只是個值，我是想成如果W是2000000000..
那麼必然就不是單純一個W可以表示時間
我的疑問是，之所以要這麼多的時間是因為?
(W=重量、V=價值)
(1)最大負重=X，n個物品，n個W，n個V"依序輸入"給電腦然後電腦一步一步
跑DP公式所導致的嗎?
(也就是說，10個物品，第一個輸入，跑一次DP，第二個物品又跑一次DP..依序)
(2)還是因為，要輸入一個物品的參數非單一所導致的?
(因為除了輸入物品個數外，還要輸入物品的重量及價值，還有最大負重)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.239.189.221
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479398446.A.F79.html
推
11/18 02:05, , 1F
11/18 02:05, 1F
剛剛發現，我們在討論的O(nW)是指局
限在我們所學這個演算法，換句話說，
我"有可能"用另一個演算法在多項式時
間內解決對吧？(如果我找到那個演算法
的話=3=
→
11/18 02:06, , 2F
11/18 02:06, 2F
→
11/18 02:06, , 3F
11/18 02:06, 3F
→
11/18 02:06, , 4F
11/18 02:06, 4F
其實這句話是我最常看到的，但是我一直不懂"意思"
n是物品數 有logn bit 若多t個bit相當物品增加t個(x個物品可x bit表示)
而最大負重W有logW bit
logn bit、logW bit這個我看不懂
我知道當W輸入1024，相當於2^10，需要10bit，不懂要表的意義但會算
也就是我第(2)所說，因為不是輸入單一參數所導致的嗎?
→
11/18 02:07, , 5F
11/18 02:07, 5F
※ 編輯: a19930301 (220.142.123.59), 11/18/2016 07:49:08
※ 編輯: a19930301 (220.142.123.59), 11/18/2016 07:53:52
※ 編輯: a19930301 (111.242.128.210), 11/18/2016 09:04:08
推
11/18 10:47, , 6F
11/18 10:47, 6F
→
11/18 10:47, , 7F
11/18 10:47, 7F
關於NPC我只知道在最後一章，我還沒讀到,現在我幾乎都心算就得最佳解(應為題目給的
項目太少)所以我覺得一定在多項式內必解，只是我現在沒那個時間去嚴格證明我的方法
，話說背包的題目還蠻少的(0/1)
推
11/18 11:04, , 8F
11/18 11:04, 8F
想問一下大大，題目是N個物品(當然還有重量,價值,最大總重等資訊)，一次給完問你最
佳取法及最大價值
還是開始給一個最大總重，然後有N個物品依序給你，問你取不取，依序到第N個，在問你
最佳解?
這兩個在考卷上是一樣(考卷又不是活的，但然全給你，在假設)
但在對電腦而言一個可一次得全資訊，另一個最後才得知全資訊，有差別
→
11/18 11:31, , 9F
11/18 11:31, 9F
推
11/18 11:48, , 10F
11/18 11:48, 10F
※ 編輯: a19930301 (111.242.128.210), 11/18/2016 14:17:39
推
11/18 22:48, , 11F
11/18 22:48, 11F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：