30- 0-1背包問題

問題描述

有 N 件物品和一個容積為 M 的背包。第 i 件物品的體積 w[i]，價值是 d[i]。求解将哪些物品裝入背包可使價值總和最大。每種物品隻有一件，可以選擇放或者不放 (N<=3500,M <= 13000)。

Example:

number＝4，capacity＝8

i	1	2	3	4
w(體積)	2	3	4	5
v(價值)	3	4	5	6

Output: 10

問題分析

（1）用 w[i] 表示物品重量，v[i] 表示物品價值。定義狀态 dp[i][j] 表示從前 i 種物品選取，使它們總體積不超過 j 的最優取法取得的價值總和。最終要求的是 dp[N][M]；

（2）初始化邊界條件，dp[0,j]=dp[i,0]=0；

（3）對于每一個物品，有兩種選擇方法，能裝下和不能裝下；

• 第一，包的容量比該商品體積小，裝不下，此時的價值與前 i-1 個的價值是一樣的，即dp[i,j]=dp[i-1,j]；
• 第二，還有足夠的容量可以裝該商品，但裝了也不一定達到目前最優價值，是以在裝與不裝之間選擇最優的一個，即dp[i,j]=max｛ dp[i-1,j]，dp[i-1,j-w(i)]+v(i) ｝其中dp[i-1,j]表示不裝，dp[i-1,j-w(i)]+v(i) 表示裝了第 i 個商品，背包容量減少 w(i) 但價值增加了 v(i)；

（4）得出遞推關系式：

• ① j<w(i) dp[i,j]=dp[i-1,j]
• ② j>=w(i) dp(i,j)=max｛ dp[i-1,j]，dp[i-1,j-w(i)]+v(i) ｝

初始化時的 dp 矩陣。初始狀态将邊界初始化為 0。j 表示背包的的重量，i 表示第 i 個物品。

一行一行将表填寫完整。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//N件物品,容積為M的背包
int knapsack(int N, int W, vector<int>weight, vector<int>value)
{
	vector<vector<int>>dp(N + 1, vector<int>(W + 1, 0));
	for (int i = 1; i <= N; i++)
	{
		int w = weight[i - 1], v = value[i - 1];
		for (int j = 1; j <= W; j++)
		{
			if (j >= w)
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
			else
				dp[i][j] = dp[i - 1][j];
		}
	}
	return dp[N][W];
}

int main() 
{
	int N, W;
	cin >> N >> W;
	vector<int>weight(N,0);
	vector<int>value(N,0);
	for (int i = 0; i < N; i++)
	{
		cin >> weight[i];
		cin >> value[i];
	}
	cout << knapsack(N, W, weight, value) << endl;
	return 0;
}
           

空間優化

由圖可以看出來，每一次 dp[i][j] 改變的值隻與 dp[i-1][x] {x:1…j}有關，也就是說隻與上一行儲存的值有關。是以，可以将 dp 寫成一維數組，優化空間，狀态轉移方程轉換為 dp[j]= max{dp[j], dp[j-w(i)]+v(i)}；

并且，狀态轉移方程，每一次推導 dp[i][j] 是通過 dp[i-1][j-w(i)] 來推導的，是以一維數組中 j 的掃描順序應該從大到小，否則前一次循環儲存下來的值将會被修改。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//N件物品,容積為M的背包
int knapsack(int N, int W, vector<int>w, vector<int>v)
{
	vector<int>dp(W + 1, 0);
	for (int i = 1; i <= N; i++)
	{
		for (int j = W; j >= w[i-1]; j--)//目前背包的剩餘容量應該大于等于該物品體積
			dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]);
	}
	return dp[W];
}

int main() 
{
	int N, W;
	cin >> N >> W;
	vector<int>w(N,0);
	vector<int>v(N,0);
	for (int i = 0; i < N; i++)
	{
		cin >> w[i];
		cin >> v[i];
	}
	cout << knapsack(N, W, w, v) << endl;
	return 0;
}