一、01背包問題

1、概述

1. 01背包中的0和1指的是放與不放，而且不能出現(xiàn)放多個的情況，背包只能放相同物品中的一個；
2. 首先是對 $d[i][j]$ 數(shù)組的解釋，該數(shù)組表示的是只看前 $i$ 個物品，總體積是 $j$ 的情況下，總價值最大是多少；

2、過程模擬

1. 不選第$i$個物品，只考慮前$i?1$個物品，$dp[i][j]=dp[i?1][j]$
2. 選第$i$個物品，$dp[i][j]=dp[i?1][j?v[i]]$
3. d p [ i ] [ j ] = m a x { 1 , 2 } dp[i][j]=max\{1,2\} dp[i][j]=max{1,2}
4. 初始條件，一個物品都不考慮$dp[0][0]=0$

背包的最大容量為 $6$。

$$?$$
$?$對于每一個單元格$i.weight>j$是否成立，按行填寫

$$?$$

$$?$$

滾動dp一維數(shù)組版

$$?$$

$$?$$

$$?$$

二、完全背包問題

1、概述

有$n$件物品，每件物品的重量為$w[i]$，價值為$c[i]$?，F(xiàn)有一個容量為$V$，的背包，問如何選取物品放入背包，使得背包物品的總價值最大。其中每件物品有無窮件。
既然這樣，不妨像0-1背包問題那樣，先寫出狀態(tài)轉(zhuǎn)移方程，從源頭上摸索。

2、閆氏dp分析完全背包問題

3、過程模擬

例如：

規(guī)律：
$?$當$j<v_i$的時候，$w_{i,j}=w_{i?1,j}$（解釋：如果當前物品裝不進背包，最大價值和前$i?1$個物品的最大價值一樣）
$?$當$j\ge v_i$的時候，$w_{i,j}=max(w_{i?1,j}$不裝，裝$)$（解釋：如果裝的下，在裝和不裝中選最大價值）

代碼模板

int m = 0;
int n = 0;
cin >> m >> n;
int v[40] = {};
int w[40] = {};
for (int i = 1; i <= n; i ++){
    cin >> v[i] >> w[i];
}
int dp[40][210] = {};
for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j) {
        if (j < v[i]) {
           dp[i][j] = dp[i - 1][j];
        }
        else {
           dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i])
        }
    }
}
cout << "max = " << dp[n][m] <<endl;

優(yōu)化版代碼：

int m = 0;
int n = 0;
cin >> m >> n;
int v[40] = {};
int w[40] = {};
for (int i = 1; i <= n; i ++){
    cin >> v[i] >> w[i];
}
int dp[40][210] = {};
for (int i = 1; i <= n; ++ i) {
    for (int j = v[i]; j <= m; ++ j) {
        dp[j] = max(dp[j], dp[j - v[i]] + w[i])
    }
}
cout << "max = " << dp[n][m] <<endl;

三、多重背包問題

1、概述

求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價值總和最大，但要注意的是，每件要取物品不能超過他給出的最大數(shù)量。

2、過程模擬

for(int i = 0; i < n; i ++)
   for(int j = m; j >= v[i]; j --)
      dp[j] = max(dp[j], dp[j - v[i]] + w[i], dp[j - 2 * v[i]] + 2 * w[i],......)//每件物品可以不去，可以取1個，或者取2個等等。

3、多重背包問題的優(yōu)化版本

假設(shè)有一種物品有 $s$ 件，若要將其拆分開來，則從 $1$ 開始循環(huán)，每進行一次循環(huán)就乘 $2$，并每循環(huán)一次就減去迭代的變量 $i$，代碼如下：

while (n--) {
	int v, w, s;
	scanf("%d%d%d", &v, &w, &s);
	for (int i = 1; i <= s; i *= 2) {
		s -= i;
		goods.push_back({ v * i,w * i });
	}
	if (s > 0)goods.push_back({ v * s,w * s });
}

分組背包問題

1、概述

有$N$組物品和一個容量是$V$的背包。每組物品有若干個，同一組內(nèi)的物品最多只能選一個。每件物品的體積是$v_{ij}$，價值是$w_{ij}$，其中$i$是組號，$j$是組內(nèi)編號。

2、過程模擬

例如：
$?$一個組只能選一個物品

以下是動態(tài)模擬：
$?$每個組都有裝和不裝兩種情況
$?$如果裝某個組的話，這個組只能裝一次文章來源地址http://www.zghlxwxcb.cn/news/detail-854940.html

3、代碼演示

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], dp[N];
int main() {
	scanf("%d%d", &n, &m);
	while (n--) {
		int s;
		scanf("%d", &s);
		for (int i = 0; i < s; i++)
			scanf("%d%d", &v[i], &w[i]);
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k < s; k++) {
				if (j >= v[k]) {
					dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
				}
			}
		}
	}
	printf("%d", dp[m]);
	return 0;
}

到了這里，關(guān)于Acwing-基礎(chǔ)算法課筆記之動態(tài)規(guī)劃（背包問題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！