01背包

N件物品和一個容量為V的背包，放入第i件物品所占的空間為Ci，得到的價值是Wi，求解將哪些物品裝入背包可使價值總和最大。 特點：每件物品只有一件，可選擇放或不放。

狀態轉移方程

F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi} F[i,v]表示將前i件物品恰放入一個容量為v的背包可獲得的最大價值 “將前i件物品放入容量為v的背包中”這個子問題，只考慮第i件物品放或不放，就可以轉化成一個只和前i-1件物品相關的問題 情況1 不放第i件物品 前i-1件物品放入容量為v的背包中，價值為F[i-1,v] 情況2 放第i件物品 前i-1件物品放入剩下的容量為v-Ci的背包中，此時能獲得的最大價值為F[i-1,v-Ci]再加上通過放入第i件物品獲得的價值Wi

空間復雜度

為了保證計算F[v]時F[v-Ci]保存的是狀態F[i-1,v-Ci]的值，要求在每次主循環中以V→v…0的遞減順序計算F[v]

偽代碼

背包問題初始化的細節問題

1 恰好裝滿背包 初始化 F[0]=0 其他F[1…v]均設為負無窮 2 沒有要求必須把背包裝滿，只希望價值最大 初始化應該將F[0…v]全部設為0

完全背包問題

有N種物品和一個容量為V 的背包，每種物品都有無限件可用。放入第i種 物品的費用是Ci，價值是Wi。求解：將哪些物品裝入背包，可使這些物品的耗 費的費用總和不超過背包容量，且價值總和最大。 從每件物品的角度考慮：取0件、取1件、取2件……直至取?V /Ci?件等許多種。 狀態轉移方程 F[i,v] = max{F[i?1,v?kCi] + kWi |0 ≤ kCi ≤ v}

優化減小其時間復雜度

若兩件物品i、j滿 足Ci ≤ Cj且Wi ≥ Wj，則將可以將物品j直接去掉，不用考慮。 比較不錯的一種方法是：首先將費用大于V 的物品去掉，然后使 用類似計數排序的做法，計算出費用相同的物品中價值最高的是哪個，可 以O(V + N)地完成這個優化。 續使用一維數組偽代碼 F[0…v]←0 for i← 1 to N for v←Ci to V F[v]←max{F[v],F[v-Ci]+Wi} 等價于 F[i,v]=max{F[i-1,v],F[i,v-Ci]+Wi} 在考慮“加選一件第i種物品”這種策略時，正需要一個可能已選入第i種物品的子結果F[i,v-Ci],必須使用v的遞增的順序循環

未完待續