我認為...背包問題在多項式內 一定 可以解決
但...在這前提是我仍不知道他的時間為何是長那樣
以下有些問題想問一下
看了一下文章都是說O(nW)的W只是個值，我是想成如果W是2000000000..
那麼必然就不是單純一個W可以表示時間
我的疑問是，之所以要這麼多的時間是因為?
(W=重量、V=價值)
(1)最大負重=X，n個物品，n個W，n個V"依序輸入"給電腦然後電腦一步一步
跑DP公式所導致的嗎?
(也就是說，10個物品，第一個輸入，跑一次DP，第二個物品又跑一次DP..依序)
(2)還是因為，要輸入一個物品的參數非單一所導致的?
(因為除了輸入物品個數外，還要輸入物品的重量及價值，還有最大負重)

01背包是弱NPC 不是多項式時間可解的個人理解：以電腦2進位角度看 n是物品數 有logn bit 若多t個bit相當物品增加t個(x個物品可x bit表示) 而最大負重W有logW bit 若多t個bit相當於原本值變2^t倍規模一個線性增長 一個指數增長 所以O(nW)才是指數時間

你有辦法找到某個多項式時間解已被證明是NLP問題的話 就推翻NLP目前的所有理論了 可以拿圖靈獎

NLP是什麼？

剛睡醒打錯了XDD 是NPC

是論文做NLP 走火入魔嗎XD

一次給完