0 - 1背包問題

什么是0 - 1背包

首先看一波百度詞條對于 “0 - 1背包問題” 的闡述：

01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2至Wn，與之相對應的價值為P1,P2至Pn，01背包是背包問題中最簡單的問題，01背包的約束條件是給定幾種物品，每種物品有且只有一個，并且有權值和體積兩個屬性，在01背包問題中，因為每種物品只有一個，對于每個物品只需要考慮選與不選兩種情況，如果不選擇將其放入背包中，則不需要處理，如果選擇將其放入背包中，由于不清楚之前放入的物品占據了多大的空間，需要列舉將這個物品放入背包后可能占據背包空間的所有情況，

是不是比較懵，那我們再對比地看一下 “背包問題” 幫助理解：

背包問題(Knapsack problem)是一種組合優化的NP完全問題，問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，我們如何選擇，才能使得物品的總價格最高，問題的名稱來源于如何選擇最合適的物品放置于給定背包中，相似問題經常出現在商業、組合數學，計算復雜性理論、密碼學和應用數學等領域中，也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達到V？它是在1978年由Merkle和Hellman提出的，

簡單來說背包問題就是能將物品分割成一部分裝入背包（實作部分裝入使得價值最大化），而 0 - 1背包呢，顧名思義，只有 0 （不裝） 和 1（裝入） 兩種選擇（這里我們討論普通背包：一件物品只能被裝入一次）；

解決實際問題

假設你現在有一個容量為8（指最多可裝質量）的背包，擺在你面前的是一些有著不同質量且價值不等的物品，具體資訊用陣串列示為weight = [ 2, 3, 4, 5] , 對應價值 value = [ 6, 7, 6, 7]，現在的問題是如何裝包使得價值最大化？

貪心思路

這里我們是不能使用貪心演算法的，若我們使用一種貪心策略：始終選擇當前物品中 rate = (value / weight) 最大的，也就是單位價值最大的物品，那么每種物品的單位價值為 unitVal = [ 3, 2.3, 1.5, 1.4]；

據此我們首先選擇 0號物品（編號從0開始），剩余容量為 8 - 2 = 6；緊接著選擇 1號物品，背包剩余容量為 6 - 3 = 3;由于不可重復裝包，剩下的兩件物品我們無法再裝入，得到最終結果 6 + 7 = 13，很顯然這是不對的，因為我們可以選擇1號與3號物品得到最大價值7 + 7 = 14；

動態規劃求解

1. 確定dp陣列以及下標的含義

這里涉及到背包容量c以及物品重量兩個維度，我們使用二維陣列來記錄每一次選取得到的最大價值，二維陣列的每一行表示一種物品，共計 weight.size() 行，陣列的每一串列示背包的容量，共計 c （背包容量）+ 1列，dp[i][j]表示在編號從 i 到 最后一號物品所構成的物品集合中且背包容量為j時取得的最優解.即從 [i : 最后一號物品] 中任意取，放進容量為 j 的背包里，價值總和最大是多少， 如dp[2][5] 表示 當背包容量為 5 時從 2 ~ 3 號物品選擇出的最大價值；同理， dp[1][8] 表示 當背包容量為 8 時從 1 ~ 3 號物品選擇出的最大價值，

2. 確定遞推公式
若當前背包容量不足以放下當前物品時（c < weight[i]）我們只能等于背包容量等于 c 且為裝入當前物品時的最優解；而當背包容量可以放下當前物品時 （c >= weight[i]），我們有兩種選擇：裝入當前物品 or 不裝入；將當前物品裝入后，背包還剩余的容量我們也能創造一定價值，這就要依賴dp陣列中之前的解情況了，而選擇不裝入，就與上一種情況一樣繼承了之前的最優解，而我們需要兩者的最大值，
因此dp公式為：

3、dp陣列如何初始化&&確定遍歷順序
根據第一點中敘述的dp陣列的含義，當背包容量為0的時候不能裝入任何物品，初始化 dp[i][0] = 0;

//注：row 為dp的行數，col 為dp的列數
for (int j = weight[row - 1]; j < col; ++j) {//當背包容量剛好放下最后一號物品時
		//初始化dp陣列 
		dp[rindex][j] = value[rindex];
	}

遍歷順序：從dp陣列最后一行從左往右自底向上(這里無特殊要求，行方向也可以從上往下遍歷)
根據遞推公式 dp[i][j] = max(dp[i + 1][j] , dp[i + 1][j - weight[i]] + value[i]) 以及遍歷順序，我們遍歷第 i 個物品時可能需要用到 “i + 1” 個物品的解情況，因此我們遍歷之前需要對dp陣列最后一行進行初始化；
具體解釋見代碼；

dp陣列詳情（讀者可自己根據遞推公式推導）：

#include <iostream>
#include <vector>
using namespace std;
//回溯背包裝包程序，將狀態記錄到x陣列中
void traceBack(vector<vector<int>>& dp, vector<int>& weight, vector<int>& x, int c) {
	int len = x.size();
	for (int i = 0; i < len - 1; i++) {
		if (dp[i][c] == dp[i + 1][c])
			x[i] = 0;
		else {
			x[i] = 1;
			c -= weight[i];
		}
	}
	x[len - 1] = (dp[len - 1][c] ? 1 : 0);
}

int ZeroOneKnapsack(vector<int>& weight, vector<int>& value, int c, vector<vector<int>>& dp) {
	//row行 c + 1列陣列
	int row = dp.size(), col = dp[0].size();
	int rindex = row - 1;
	for (int j = weight[row - 1]; j < col; ++j) {//當背包容量剛好放下最后一號物品時
		//初始化dp陣列
		dp[rindex][j] = value[rindex];
	}
	rindex--;
	//rindex即 行下標 ，cindex為列下標
	for (; rindex >= 0; rindex--) {
		for (int cindex = 0; cindex < col; cindex++) {
			if (cindex < weight[rindex]) {
				//當前容量不足以裝下當前物品，價值來源于上一行（此處沒裝）
				dp[rindex][cindex] = dp[rindex + 1][cindex];
			}
			else {
				//兩種情況：1、裝入當前物品，當前物品的價值加上剩余容量能創造的價值
				//2、不裝入當前物品，價值等于dp陣列上一行的數值
				dp[rindex][cindex] = max(dp[rindex + 1][cindex], dp[rindex + 1][cindex - weight[rindex]] + value[rindex]);
			}
		}
	}
	return dp[0][col - 1];
}

int main() {
	vector<int> weight{ 2,3,4,5 };//各物品質量
	vector<int> value{ 6,7,6,7 };//對應物品的價值
	int c = 8;//背包容量
	vector<vector<int>> dp(weight.size(), vector<int>(c + 1));//創建二維dp陣列
	cout << "背包可以裝入物品的最大價值為" << ZeroOneKnapsack(weight, value, c, dp) << endl;
	vector<int> x(weight.size(), 0);//記錄物品的裝包情況 
	traceBack(dp,weight,x,c);
	for (int i = 0; i < x.size(); i++) {
		if (x[i])
			cout << i << "號物品被放入背包, 價值為" << value[i] << endl;
	}
	return 0;
}

運行效果

空間優化

這里使用的二維陣列實質上可以用一個一維陣列代替，根據遞推公式

當前背包的最大值取決于上一次遍歷得到的最優解， 使用一維動態陣列時需要注意：不能再從左至右遍歷：
假設當前遍歷的物品編號為i，weight[i] = 1，價值value[i] = 15, 且dp[0] = 0;
如從左至右遍歷：（dp[i] 表示 背包容量為 i 時取得的最大值）

• dp[1] = max(dp[1 - 1], dp[1 - weight[i] ] + value[i]) = dp[0] + 15 = 15; 1 >= weight[i];
• dp[2] = max(dp[2 - 1], dp[2 - weight[i] ] + value[i]) = dp[1] + 15 = 30; 2>=weight[i]
  很顯然這里對當前物品進行了重復裝包，而在當前問題中這是不允許的，所以我們必須從右往左逆序遍歷，可以根據遞推公式嘗試推導從右往左遍歷時dp陣列的取值情況（避免了重復取同一個物品）；

代碼如下：

int ZeroOneKnapsack(vector<int>& weight, vector<int>& value, int c) {
	int nums = weight.size(), col = c + 1;
	vector<int> dp(c + 1, 0);//初始化一維陣列dp長度為 c + 1且所有元素為0
	int curNo = nums - 1;//當前遍歷的物品編號
	for (int i = nums - 1; i >= 0; i--) {//當前物品
		for (int j = c; j >= weight[i]; j--) {//背包當前容量
			dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
	}
	cout << dp[c] << endl;
	return dp[c];
}

說明（小聲bb）

科班大二在讀，菜鳥一名，正修演算法，博客主要用于記錄自己對于一些經典題的理解和以及提升代碼實作能力，均為課后根據思路（思路來源：上課老師講解、課下查閱相關資料）原創完成，有表述不清或思路混亂的地方還請寬恕以及評論告知，一起學習一起進步，歡迎大家指正~~~