背包問題可以通過動態規劃解決，為什麼還說背包問題是NPC的？

01-12

或者說這兩個背包問題不是同一個問題？

0-1背包的複雜度是O(nW)，n是物品數量，W是背包最大承載重量。

W的值是根據輸入規模指數變化的（注意這裡的輸入規模是二進位位，比如10位，W最大值就為1023；11位，W最大值就為2047）。

為什麼要關心二進位位？因為在計算機底層，輸入規模就是二進位位的大小。

所以O(nW)相對輸入規模就是指數級的。

什麼是偽多項式時間演算法

大家都回答得差不多了，我就來寫得正式一點吧。

假設輸入是 $W,w_1,w_2,...,w_n,v_1,v_2,...,v_n$ 。

$W$ 表示背包大小， $w_i$ 表示每個物體的大小， $v_i$ 表示每個物體的價值。

輸入規模（輸入的二進位編碼長度） $N=log W + sum_i^nlog w_i+sum_i^nlog v_i > log W$

動態規劃演算法的時間複雜度為 $nW$ 。然而 $nW=n*2^{log W}$ 並不能夠表示為 $O(p(N))$ ，其中 $p(N)$ 為任意多項式。

所以動態規劃演算法不是多項式時間複雜度的，所以也不能證明背包問題是P問題。

至於為什麼背包問題是NPC問題，大家可以查看其他資料，我相信問題並不是想問這個。

PS：為什麼我們討論演算法時間複雜度時，要用輸入的二進位編碼表示其輸入規模？

當我們討論一個演算法的時間複雜度時，是在說演算法運行時間與其輸入規模的關係。

用正式一點的語言來說，一個演算法就是一台確定性圖靈機M，M對於長度為N的輸入串，能夠在某個函數T(N)的時間內輸出結果，這個函數T(N)就是這台圖靈機的時間複雜度。

一個問題實例的規模就是指它被編碼到圖靈機的輸入帶上的長度。可以證明的是，用任何有限的字符集來編碼，T(N)本質上都不會變，只是會乘上某個常數因子。所以通常我們用輸入的二進位編碼長度來表示輸入規模。

PPS：實際上我覺得說動態規劃演算法時間複雜度為 $nW$ 時暗含了 $w_i,v_i$ 都是小於某個常數的，這樣一些對於數的操作才能在常數時間內完成。

PPPS：這個問題下看到了好幾位我校大神...ORZ

如果你真的想搞清楚這個問題的話，你需要先看很多資料。

首先，你需要看看NPC問題是怎麼定義的，尤其是如何判斷時間複雜度是否多項式時間。(注重看怎麼encoding，然後時間複雜度n是哪個n)

其實，背包問題的解的時間複雜度，跟總價值是多項式關係的，這是偽多項式時間複雜度，因為總價值不是輸入的那個n。

這個我一時間解釋不好，建議看看NPC問題的定義，和背包問題用動態規劃解決後，時間複雜度的式子。

背包的複雜度受物品總價值影響，總價值與輸入規模不存在多項式關係，輸入規模極小也可以達到很大的複雜度。@符茂松所說是對的。

————————————————————————————————————————

下面是題主原問題的答案……

背包貌似不適用普通的線性規劃，應該視為整數規劃，可以認為是一個0-1規劃模型。

而整數規劃或0-1規劃似乎沒有多項式解法

因為價格和重量不總是離散的

NPC不意味著沒有解法，只是解法不是多項式複雜度度的。。。高於多項式複雜度的所以是NPC啊

https://courses.csail.mit.edu/6.006/fall11/rec/rec21_knapsack.pdf

引用一個之前看到的回答：

利用動態規劃的確是O（n*w）的時間複雜度，但是要知道，n的確是輸入規模的一部分，輸入了n個重量與價值，但是w並不是輸入規模，對於一個數W，需要m=log w的位數來表示.因此，m才是輸入規模的一部分。所以O（n*w）=O（n2^m）,所以是NPC問題。

背包DP的時間複雜度是指數級的，不是多項式級。動態規劃是一類演算法，這類演算法的複雜度可以是線性的，也可以是指數級。