Can you summarize the following document?
        
  我們有 "n" 種物品,物品 "j" 的重量為"w",價格為"p"。 我們假定所有物品的重量和價格都是非負的。揹包所能承受的最大重量為"W"。 如果限定每種物品只能選擇0個或1個,則問題稱為0-1揹包問題。 可以用公式表示為:  如果限定物品"j"最多隻能選擇"b"個,則問題稱為有界揹包問題。 可以用公式表示為:  如果不限定每種物品的數量,則問題稱為無界揹包問題。 各類複雜的揹包問題總可以變換為簡單的0-1揹包問題進行求解。

  在電腦科學領域,人們對揹包問題感興趣的原因在於:

  

  如果重量"w",..., "w"和"W"都是非負數,那麼用動態規劃,可以用偽多項式時間解決揹包問題。下面描述了無界揹包問題的解法。  簡便起見,我們假定重量都是正數(w > 0)。在總重量不超過"W"的前提下,我們希望總價格最高。對於"Y" ≤ "W",我們將在總重量不超過"Y"的前提下,總價格所能達到的最高值定義為"A"("Y")。"A"("W")即為問題的答案。  顯然,"A"("Y")滿足: 其中,"p"為第"j"種物品的價格。  關於第二個公式的一個解釋:總重量為"Y"時揹包的最高價值可能有兩種情況,第一種是該重量無法被完全填滿,這對應於表示式"A"("Y - 1")。第二種是剛好填滿,這對應於一個包含一系列剛好填滿的可能性的集合,其中的可能性是指當最後放進包中的物品恰好是重量為"w"的物品時揹包填滿並達到最高價值。而這時的揹包價值等於重量為"w"物品的價值"p"和當沒有放入該物品時揹包的最高價值之和。故歸納為表示式"p" + "A"("Y" - "w")。最後把所有上述情況中揹包價值的最大值求出就得到了"A"("Y")的值。  如果總重量為0,總價值也為0。然後依次計算"A"(0), "A"(1),..., "A"("W"),並把每一步驟的結果存入表中供後續步驟使用,完成這些步驟後"A"("W")即為最終結果。由於每次計算"A"("Y")都需要檢查"n"種物品,並且需要計算"W"個"A"("Y")值,因此動態規劃解法的時間複雜度為O("nW")。如果把"w",..., "w", "W"都除以它們的最大公因數,演算法的時間將得到很大的提升。  儘管揹包問題的時間複雜度為O("nW"),但它仍然是一個NP完全問題。這是因為"W"同問題的"輸入大小"並不成線性關係。原因在於問題的輸入大小僅僅取決於表達輸入所需的位元數。事實上,formula_5,即表達"W"所需的位元數,同問題的輸入長度成線性關係。

  類似的方法可以解決0-1揹包問題,演算法同樣需要偽多項式時間。我們同樣假定"w",..., "w"和"W"都是正整數。我們將在總重量不超過"Y"的前提下,前"j"種物品的總價格所能達到的最高值定義為"A"("j", "Y")。  "A"("j", "Y")的遞推關係為:  通過計算"A"("n", "W")即得到最終結果。為提高演算法效能,我們把先前計算的結果存入表中。因此演算法需要的時間和空間都為O("nW"),通過對演算法的改進,空間的消耗可以降至O("W")。

  推廣的揹包問題有二次揹包問題、多維揹包問題、多目標揹包問題等。  二次揹包問題是揹包問題的一種推廣形式:
揹包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定揹包中。