動态規劃——背包問題

動态規劃

動态規劃的優化涉及到一般就是對動态規劃的代碼或方程做一個等價變形

0,1背包問題

描述

N個物品和容量為V的背包，每一個物品有兩個屬性 {重量\(w_i\),價值\(v_i\)}, 每件物品最多僅能用一次。

在背包能裝得下的情況下，能選出的物品最大總價值為多少。

思路

先把基本的形式寫出來，再一點點優化。背包問題的最優形式是用一維數組來表示，但是我們考慮一定要從最樸素的情況來考慮，然後再考慮優化。

從集合的角度來了解DP問題，DP中的每一個狀态都表示一個集合，需要考慮清楚，f[i][j]表示的是哪一個集合，如背包問題就是所有選法的集合。

但實際上f[i][j]存儲的是一個數，這個數就是集合的某種屬性。集合表示什麼呢？

集合表示的就是選法，即究竟選擇了哪種選法，是選了第1，2，3個物品還是第4，5個物品，這個集合需要滿足兩個條件：

1. 隻從前i個物品中選
2. 選出來的物品的總體積 \(\le\) j

滿足這兩個條件的所有選法的集合就是f[i][j]表示的集合，f[i][j]存儲的是所有選法的價值的最大值。

具體如下圖所示：

狀态計算就是考慮f[i][j]可以被怎樣計算出來，把所有的f[i][j]計算出來後，最終結果應為f[N][v]。

表示所有從前N個物品中選擇出總體積 \(\le\) v的集合的總價值的最大值。

通過不停的将目前集合劃分成若幹個更小的集合，使每一個集合都可以用前面更小的集合表示出來。

如圖中，将f[i][j]劃分為包含i和不包含i這兩個集合。

集合劃分的原則：

1. 不重複，一個元素不要出現在兩個集合，有些時候可以不滿足
2. 不漏，必須滿足。

完全背包問題

N個物品和容量為V的背包，每一個物品有兩個屬性 {重量\(w_i\),價值\(v_i\)}, 每件物品有無限個。

多重背包問題

N個物品和容量為V的背包，每一個物品有兩個屬性 {重量\(w_i\),價值\(v_i\)}, 每件物品最多有\(s_i\)個。

分組背包問題