在如今的面試當中算法題已經成為面試不可或缺的內容，今天就跟大家分享一個還比較困難的筆試題——完全背包。
完全背包問題
有N種物品和一個容量是 V的背包，每種物品都有無限件可用。第i 種物品的體積是 vi，價值是wi。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
完全背包問題和01背包的唯一區別就在於物品的個數，在01背包當中所有的物品只有一件，也就只能使用一次。而在完全背包當中物品可以使用無限多次。
比如下面的4個物品，背包能夠承受的最大重量為5，我們應該如何選擇，使得我們獲得的總價值最大：
|
物品 |
重量 |
價值 |
|
A |
1 |
2 |
|
B |
2 |
4 |
|
C |
3 |
4 |
|
D |
4 |
5 |
這個問題還是比較簡單，我們直接從圖中看，我們可以選擇五個A或者兩個B一個A，可以產生最大的收益，最大收益為10。
完全背包問題分析
01背包動態轉移方程分析
在01背包問題當中，我們是使用一個二維數組dp[i][j]進行計算，dp[i][j]表示在只使用前i個物品且背包容量為j的情況下，我們能夠獲得的最大的收益。在這個情況下，我們根據當前背包容量j判斷是否能裝入第i個物品可以得到下面兩個方程（下面公式字母的含義與上文完全背包問題所提到的一致）。
dp[i][j]={max(dp[i−1][j−v[i]]+w[i],dp[i−1][j]),j≥v[i]dp[i−1][j],j<v[i]
上面01背包的公式的第二條比較簡單，如果背包容量不足以容納第i件物品，那麼只能從前i - 1物品當中選擇了。我們來仔細分析一下第一條公式。
如果當前背包容量可以容納第i個物品，那麼我們就可以選擇第i件物品或者不選擇，我們應該選擇兩種選擇當中收益更大的那個。
- 如果我們不選擇第i個物品，那麼我們就能夠使用容量為j的背包去選擇前i - 1個物品，這種情況下我們的最大收益為dp[i - 1][j]。
- 如果選擇第i個物品，那麼我們背包容量還剩下j - v[i]，還可以選擇剩下的i - 1個物品，而且我們的收益需要加上w[i]，因此我們的收益為max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。
完全背包動態轉移方程分析
和01背包問題一樣首先對於第i個物品，首先需要判斷背包是否能夠容納：
- 如果背包的容量大於等於第i個物品的體積，那我們就有兩種選擇：將第i個物品放入背包當中，但是在這裡需要注意的一點是完全背包的物品有無數件，因此當我們選擇之後我們的轉移方程為dp[i][j - v[i]] + w[i]，這裡不是i-1而是i，因為第i件物品有無數件。不將第i個物品放入背包當中，那麼我們就能夠使用容量為j的背包去選擇前i - 1個物品，這種情況下我們的最大收益為dp[i - 1][j]。
- 如果背包容量小於第i件物品的體積，我們就不能夠選擇第i件物品了，這種情況下我們的最大收益為dp[i - 1][j]。
基於上面的分析我們可以知道完全背包問題的動態轉移方程為：
dp[i][j]={max(dp[i][j−v[i]]+w[i],dp[i−1][j]),j≥v[i]dp[i−1][j],j<v[i]
背包問題代碼構成設計
根據對動態轉移方程的分析，我們可以知道，我們在計算dp[i][j]這個數據的值的時候，我們首先需要將dp[i][j - v[i]]和dp[i - 1][j])的結果計算出來，因為dp[i][j]依賴這兩個數據。
根據上面的分析和圖我們知道，在計算dp[i][j]之前，我們需要將第i行第j列之前的數據和dp[i - 1][j]都計算出來，因為dp[i][j]依賴這些數據。而我們最終需要的結果是dp[N][V]表示在背包容量為V且能夠選擇前N個物品（也就是所有物品）能夠獲得的最大的收益，所以我們最終需要求出dp[N][V]的值。
因此基於以上分析，我們要想最終解出dp[N][V]的值，我們可以採取兩重for循環，第一重循環遍歷物品，第二重循環遍歷容量，但是我們的第0行沒有前一行，因此我們需要對第0行進行初始化：
// 對第0行進行初始化操作for (int i = 0; i <= V; ++i) { // 如果只能選擇第一個數據，而且能選無數次 // 那就將所有的容量都拿來裝第一個物品 dp[0][i] = i / v[0] * w[0];}根據動態轉移方程，我們有下面的代碼：
for (int i = 1; i < N; ++i) { for (int j = 0; j <= V; ++j) { if (j >= v[i]) { dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]); } else { dp[i][j] = dp[i - 1][j]; } }}C++完整代碼如下：
#include <iostream>using namespace std;#define MAX_LEN 10000 int w[MAX_LEN];int v[MAX_LEN];int dp[MAX_LEN][MAX_LEN];int N, V; int backpack() { // 對第0行進行初始化操作 for (int i = 0; i <= V; ++i) { // 如果只能選擇第一個數據，而且能選無數次 // 那就將所有的容量都哪來裝第一個物品 dp[0][i] = i / v[0] * w[0]; } for (int i = 1; i < N; ++i) { for (int j = 0; j <= V; ++j) { if (j >= v[i]) { dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[N - 1][V];}Java代碼如下：
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N]; int[] v = new int[N]; int[][] dp = new int[N][V + 1]; for (int i = 0; i < N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } // 對第0行進行初始化操作 for (int i = 0; i <= V; ++i) { // 如果只能選擇第一個數據，而且能選無數次 // 那就將所有的容量都哪來裝第一個物品 dp[0][i] = i / v[0] * w[0]; } for (int i = 1; i < N; ++i) { for (int j = 0; j <= V; ++j) { if (j >= v[i]) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - v[i]] + w[i]); } else { dp[i][j] = dp[i - 1][j]; } } } System.out.println(dp[N - 1][V]);}完全背包數組優化
在前面的內容當中我們已經仔細分析了完全背包問題的動態轉移方程，我們發現在兩層循環的內層循環當中，必須從0遍歷到V，因為我們後面的數據依賴同一行前面的數據，還有就是依賴上一行相同列的數據，比如dp[i][j]依賴dp[i][0]到dp[i][j - 1]，還依賴dp[i - 1][j]，這個其實是可以只用一個數組進行計算的。
我們先來看單行完全背包的Java代碼：
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N]; int[] v = new int[N]; int[] dp = new int[V + 1]; for (int i = 0; i < N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } for (int i = 0; i < N; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]); } } System.out.println(dp[V]);}下面我們舉個使用單行數組優化的例子：
假如我們正在更新dp[j]，此時dp[j]還是第i-1行的狀態而dp[0]到dp[j-1]已經是第i行的狀態了，因為我們是從前到後進行遍歷。而要計算dp[j]的第i行狀態的結果，那麼他需要dp[0]到dp[j-1]的第i行狀態的數據，dp[j]的第i-1行狀態的數據，而實際情況數組能夠滿足這種依賴關係，因此我們可以使用單行數組優化。
這個單行數組與多行數組的區別是多行數組每一行有每一行的狀態，而且他保存了所有行的狀態，單行數組只存在一行的狀態，但是他會經歷所有行的狀態，也就是在外層for循環下單行數組的狀態不斷更新。（如果你不理解這段話和上面談到的單行數組優化，可以結合代碼和文字進行理解）
C++代碼：
#include <iostream>using namespace std;#define MAX_LEN 10000 int w[MAX_LEN];int v[MAX_LEN];int dp[MAX_LEN]int N, V; int backpack() { for (int i = 0; i < N; ++i) { for (int j = v[i]; j <= V; ++j) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } return dp[V];} int main() { cin >> N >> V; for (int i = 0; i < N; ++i) { cin >> v[i] >> w[i]; } cout << backpack(); return 0;}總結
在仔細分析完完全背包問題之後，我們可以總結一下動態規劃的套路：
- 分析問題設置dp數組並分析數組的含義。
- 尋找動態轉移方程，分析dp數組當中數據之間的依賴關係，我們在疊代的時候一定要遵循這個關係。
- 初始化數組。
- 進行數組dp求解。
- 分析動態轉移方程的含義和數據依賴關係，分析是否能夠在不破壞數據依賴關係的條件下，優化數組空間。
其實上面的套路對於大多數動態規劃的題目都有用的，因為動態規劃的流程基本一致，而動態規劃最難的地方就是第一步了，通過分析問題尋找動態轉移方程。