轉自：劉毅
https://www.61mon.com/index.php/archives/188/
好文投稿， 請點擊 → 這裡了解詳情
問題展開
有 N 件物品和一個容量為 V 的背包。第 i 件物品的體積是 Ci，其價值是 Wi。求解，在不超過背包容量情況下，將哪些物品裝入背包可使價值總和最大。
基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件。
狀態 F[i,v] 表示前 i 件物品中選擇若干件放在容量為 v 的背包中，可以取得的最大價值。
轉移方程：
對於第 i 件物品，有放與不放兩種選擇。若選擇不放，F[i,v]=F[i−1,v]；若選擇放，v−Ci 確保有足夠的空間，隨之 F[i,v]=F[i−1,v−Ci]+Wi。
代碼展開
/**
*
* author 劉毅（Limer）
* date 2017-03-17
* mode C++
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
const int N = 6; // 物品個數
const int V = 10; // 背包體積
// 第 i 個物品的體積（下標從 1 開始）
int C[N + 1] = { -1,5,6,5,1,19,7 };
// 第 i 個物品的價值
int W[N + 1] = { -1,2,3,1,4,6,5 };
// 狀態
int F[N + 1][V + 1] = { 0 };
// 對於第 i 個物品
for (int i = 1; i <= N; i++)
for (int v = 0; v <= V; v++)
{
F[i][v] = F[i - 1][v]; //第 i 個不放
// 如果比它大，再放第 i 個
if (v - C[i] >= 0 && F[i][v] < F[i - 1][v - C[i]] + W[i])
F[i][v] = F[i - 1][v - C[i]] + W[i];
}
cout<< F[N][V] << endl;
return 0;
}
以上方法的時間和空間複雜度均為 O(VN)，其中時間複雜度應該已經不能再優化了，但空間複雜度卻可以優化到 O(V)。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i ← 1 to N，每次算出來二維數組 F[i,v] 的所有值。
那麼，如果只用一個數組 F[v] 能不能保證第 i 次循環結束後 F[v] 中表示的就是我們定義的狀態 F[i,v] 呢？
F[i,v] 是由 F[i−1,v] 和 F[i−1,v−Ci] 兩個子問題遞推而來，能否保證在推 F[i,v] 時（也即在第 i 次主循環中推 F[v] 時）能夠取用 F[i−1,v] 和 F[i−1,v−Ci] 的值呢？
事實上，這要求在每次主循環中我們以v ← V to C[i]的遞減順序計算 F[v]，這樣才能保證計算 F[v] 時 F[v−Ci] 保存的是狀態 F[i−1,v−Ci] 的值。
優化後的代碼如下：
/**
*
* author 劉毅（Limer）
* date 2017-03-17
* mode C++
*/
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
const int N = 6; // 物品個數
const int V = 10; // 背包體積
// 第 i 個物品的體積（下標從 1 開始）
int C[N + 1] = { -1,5,6,5,1,19,7 };
// 第 i 個物品的價值
int W[N + 1] = { -1,2,3,1,4,6,5 };
int F[V + 1] = { 0 }; // 狀態
for (int i = 1; i <= N; i++) // 對於第 i 個物品
for (int v = V; v >= C[i]; v--)
F[v] = max(F[v], F[v - C[i]] + W[i]);
cout << "最大價值是：" << F[V] << endl;
return 0;
}
初始化的細節問題
我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求 「恰好裝滿背包」 時的最優解，有的題目則並沒有要求必須把背包裝滿。
這兩種問法的實現方法只是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了 F[0] 為 0，其它 F[1]...F[V] 均設為−∞，這樣就可以保證最終得到的 F[V] 是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格儘量大，初始化時應該將 F[0]...F[V] 全部設為 0。
這是為什麼呢？可以這樣理解：初始化的 F 數組事實上就是在沒有任何物品可以放入背包時的合法狀態。
如果要求背包恰好裝滿，那麼此時只有容量為 0 的背包可以在什麼也不裝且價值為 0 的情況下被 「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，應該被賦值為 -∞了。
如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解 「什麼都不裝」，這個解的價值為 0，所以初始時狀態的值也就全部為 0 了。
參考文獻
背包九講.
覺得本文有幫助？請分享給更多人
關注「算法愛好者」，修煉編程內功