Re: [理工] 演算法 0-1knapscak觀念疑問

[a19930301 (-手起刀落o`)]

我認為...背包問題在多項式內 一定 可以解決

但...在這前提是我仍不知道他的時間為何是長那樣

以下有些問題想問一下

看了一下文章都是說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
推 w181496: 01背包是弱NPC 不是多項式時間可解的
剛剛發現，我們在討論的O(nW)是指局
限在我們所學這個演算法，換句話說，
我"有可能"用另一個演算法在多項式時
間內解決對吧？(如果我找到那個演算法
的話=3=
→ w181496: 個人理解：以電腦2進位角度看 n是物品數 有logn bit 若多
→ w181496: t個bit相當物品增加t個(x個物品可x bit表示) 而最大負重W
→ w181496: 有logW bit 若多t個bit相當於原本值變2^t倍規模
其實這句話是我最常看到的，但是我一直不懂"意思"
n是物品數 有logn bit 若多t個bit相當物品增加t個(x個物品可x bit表示)
而最大負重W有logW bit

logn bit、logW bit這個我看不懂
我知道當W輸入1024，相當於2^10，需要10bit，不懂要表的意義但會算
也就是我第(2)所說，因為不是輸入單一參數所導致的嗎?

→ w181496: 一個線性增長 一個指數增長 所以O(nW)才是指數時間
※ 編輯: 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
推 aa06697: 你有辦法找到某個多項式時間解已被證明是NLP問題的話 就
→ aa06697: 推翻NLP目前的所有理論了 可以拿圖靈獎
關於NPC我只知道在最後一章，我還沒讀到,現在我幾乎都心算就得最佳解(應為題目給的
項目太少)所以我覺得一定在多項式內必解，只是我現在沒那個時間去嚴格證明我的方法
，話說背包的題目還蠻少的(0/1)
推 FRAXIS: NLP是什麼？
想問一下大大，題目是N個物品(當然還有重量,價值,最大總重等資訊)，一次給完問你最
佳取法及最大價值

還是開始給一個最大總重，然後有N個物品依序給你，問你取不取，依序到第N個，在問你
最佳解?

這兩個在考卷上是一樣(考卷又不是活的，但然全給你，在假設)

但在對電腦而言一個可一次得全資訊，另一個最後才得知全資訊，有差別
→ aa06697: 剛睡醒打錯了XDD 是NPC
推 goldflower: 是論文做NLP 走火入魔嗎XD
※ 編輯: a19930301 (111.242.128.210), 11/18/2016 14:17:39
推 FRAXIS: 一次給完