? 作者主頁：歡迎來到我的技術(shù)博客??
? 個(gè)人介紹：大家好，本人熱衷于Java后端開發(fā)，歡迎來交流學(xué)習(xí)哦！(￣▽￣)~*
?? 如果文章對(duì)您有幫助，記得關(guān)注、點(diǎn)贊、收藏、評(píng)論??????
?? 您的支持將是我創(chuàng)作的動(dòng)力，讓我們一起加油進(jìn)步吧?。?！????
第一章 背包問題
一、01背包問題
1. 題目描述
有 N 件物品和一個(gè)容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的體積是 v i v_i vi?，價(jià)值是 w i w_i wi?。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品數(shù)量和背包容積。
接下來有 N 行，每行兩個(gè)整數(shù) v i , w i v_i,w_i vi?,wi?，用空格隔開，分別表示第 ii 件物品的體積和價(jià)值。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi?,wi?≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例：
8
2. 思路分析
版本一： 二維數(shù)組
（1）狀態(tài) f[i][j] 定義：前
i
i
i 個(gè)物品，背包容量是
j
j
j 下的最優(yōu)解（最大價(jià)值）：
- 當(dāng)前的狀態(tài)依賴于之前的狀態(tài)，可以理解為從初始狀態(tài)
f[0][0] = 0開始決策，有 N 件物品，則需要 N 次決 策，每一次對(duì)第 i i i 件物品的決策，狀態(tài)f[i][j]不斷由之前的狀態(tài)更新而來。
(2) 當(dāng)前背包容量不夠（j < v[i]），沒得選，因此前
i
i
i 個(gè)物品最優(yōu)解即為前
i
?
1
i?1
i?1 個(gè)物品最優(yōu)解：
- 狀態(tài)轉(zhuǎn)移方程：
f[i][j] = f[i - 1][j]
(3) 當(dāng)前背包容量夠，可以選，因此需要決策選與不選第 i i i 個(gè)物品：
- 選：
f[i][j] = f[i - 1][j - v[i]] + w[i] - 不選：
f[i][j] = f[i - 1][j] - 我們的決策是如何取到最大價(jià)值，因此以上兩種情況取 最大值。
代碼如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N]; // 體積
int w[N]; // 價(jià)值
int f[N][N]; // f[i][j], j體積下前i個(gè)物品的最大價(jià)值
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
// 當(dāng)前背包容量裝不進(jìn)第i個(gè)物品，則價(jià)值等于前i-1個(gè)物品
if(j < v[i])
f[i][j] = f[i - 1][j];
// 能裝，需進(jìn)行決策是否選擇第i個(gè)物品
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}
版本二： 一維數(shù)組
將狀態(tài) f[i][j] 優(yōu)化到一維 f[j]，實(shí)際上只需要做一個(gè)等價(jià)變形。
為什么可以這樣變形呢？我們定義的狀態(tài) f[i][j] 可以求得任意合法的
i
i
i 與
j
j
j 最優(yōu)解，但題目只需要求得最終狀態(tài) f[n][m] ，因此我們只需要一維的空間來更新狀態(tài)。
(1) 狀態(tài) f[j] 定義：N 件物品，背包容量
j
j
j 下的最優(yōu)解。
(2) 注意枚舉背包容量 j j j 必須從 m m m 開始。
(3) 為什么一維情況下枚舉背包容量需要逆序？ 在二維情況下，狀態(tài) f[i][j] 是由上一輪i - 1的狀態(tài)得來的，f[i][j] 與 f[i - 1][j] 是獨(dú)立的。而優(yōu)化到一維后，如果我們還是正序，則有f[較小體積] 更新到f[較大體積]，則有可能本應(yīng)該用第i-1 輪的狀態(tài)卻用的是第 i 輪的狀態(tài)。
(4) 例如，一維狀態(tài)第 i 輪對(duì)體積為 3 的物品進(jìn)行決策，則 f[7] 由 f[4] 更新而來，這里的 f[4] 正確應(yīng)該是 f[i - 1][4]，但從小到大枚舉j這里的 f[4] 在第i輪計(jì)算卻變成了 f[i][4]。當(dāng)逆序枚舉背包容量j時(shí)，我們求 f[7] 同樣由 f[4] 更新，但由于是逆序，這里的 f[4] 還沒有在第 i 輪計(jì)算，所以此時(shí)實(shí)際計(jì)算的 f[4] 仍然是 f[i - 1][4]。
(5) 簡單來說，一維情況正序更新狀態(tài) f[j] 需要用到前面計(jì)算的狀態(tài)已經(jīng)被「污染」，逆序則不會(huì)有這樣的問題。
(6) 狀態(tài)轉(zhuǎn)移方程： f[j] = max(f[j], f[j - v[i]] + w[i]
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
{
if(j < v[i])
f[i][j] = f[i - 1][j]; // 優(yōu)化前
f[j] = f[j]; // 優(yōu)化后，該行自動(dòng)成立，可省略。
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); // 優(yōu)化前
f[j] = max(f[j], f[j - v[i]] + w[i]); // 優(yōu)化后
}
實(shí)際上，只有當(dāng)枚舉的背包容量 j>= v[i] 時(shí)才會(huì)更新狀態(tài)，因此我們可以修改循環(huán)終止條件進(jìn)一步優(yōu)化。
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
關(guān)于狀態(tài) f[j] 的補(bǔ)充說明:
二維下的狀態(tài)定義 f[i][j] 是前
i
i
i 件物品，背包容量
j
j
j 下的最大價(jià)值。一維下，少了前
i
i
i 件物品這個(gè)維度，我們的代碼中決策到第
i
i
i 件物品（循環(huán)到第i輪），f[j] 就是前i輪已經(jīng)決策的物品且背包容量
j
j
j 下的最大價(jià)值。
因此當(dāng)執(zhí)行完循環(huán)結(jié)構(gòu)后，由于已經(jīng)決策了所有物品，f[j] 就是所有物品背包容量
j
j
j 下的最大價(jià)值。即一維 f[j] 等價(jià)于二維 f[n][j]。
版本三： 優(yōu)化輸入
我們注意到在處理數(shù)據(jù)時(shí)，我們是一個(gè)物品一個(gè)物品，一個(gè)一個(gè)體積的枚舉。
因此我們可以不必開兩個(gè)數(shù)組記錄體積和價(jià)值，而是邊輸入邊處理。
代碼如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
int v, w;
cin >> v >> w; // 邊輸入邊處理
for(int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m] << endl;
return 0;
}
3. 代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
二、完全背包問題
1. 題目描述
有 N 種物品和一個(gè)容量是 V 的背包，每種物品都有無限件可用。
第 i i i 種物品的體積是 v i v_i vi?，價(jià)值是 w i w_i wi?。
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。
接下來有 N 行，每行兩個(gè)整數(shù) v i , w i v_i,w_i vi?,wi?，用空格隔開，分別表示第 i i i 種物品的體積和價(jià)值。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0
<
N
,
V
≤
1000
0<N,V≤1000
0<N,V≤1000
0
<
v
i
,
w
i
≤
1000
0<v_i,w_i≤1000
0<vi?,wi?≤1000
輸入樣例
4 5
1 2
2 4
3 4
4 5
輸出樣例：
10
2. 思路分析
版本一： 二維數(shù)組
狀態(tài)變量：f[i][j] 表示前
i
i
i 件物品放入容量為
j
j
j 的背包的最大價(jià)值。
當(dāng)前背包容量為 j j j，我們要考慮 i i i 件物品能否放入？是否放入？
-
當(dāng)前背包容量
j < w[i]，不能放入，則f[i][j] = f[i - 1][j] -
當(dāng)前背包容量
j > w[i]，能放入，但要考慮代價(jià)- 若第
i
i
i 件物品不放入背包，則
f[i][j] = f[i - 1][j] - 若第
i
i
i 件物品放入背包，則
f[i][j] = f[i][j - w[i]] + c[i]
- 若第
i
i
i 件物品不放入背包，則
對(duì)于前
i
i
i 件物品，背包容量為 j - w[i] 時(shí)可能已經(jīng)放入了第
i
i
i 件物品，容量為
j
j
j 時(shí)還可以再放入第
i
i
i 件物品，所以用 f[i][j - w[i]] 更新 f[i][j]。
代碼實(shí)現(xiàn)如下：
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (j < w[i])
f[i][j] = f[i - 1][j];
else
f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + c[i]);
}
}
cout << f[n][m] << endl;
版本二： 一維數(shù)組
用一維數(shù)組 f[j] 只記錄一行數(shù)據(jù)，讓
j
j
j 值順序循環(huán)，順序更新 f[j]值。
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (j < w[i])
f[j] = f[j];
else
f[j] = max(f[j], [j - w[i]] + c[i]);
}
}
cout << f[m] << endl;
實(shí)際上，只有當(dāng)枚舉的背包容量 j>= v[i] 時(shí)才會(huì)更新狀態(tài)，因此我們可以修改循環(huán)終止條件進(jìn)一步優(yōu)化。
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
3. 代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i]>> w[i];
for (int i = 1; i <= n; i ++)
for (int j = v[i]; j <= m; j ++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
三、多重背包問題I
1. 題目描述
有 N 種物品和一個(gè)容量是 V 的背包。
第 i i i 種物品最多有 s i s_i si? 件，每件體積是 v i v_i vi?，價(jià)值是 w i w_i wi?。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。
接下來有 N 行，每行三個(gè)整數(shù) v i , w i , s i v_i,w_i,s_i vi?,wi?,si?，用空格隔開，分別表示第 i i i 種物品的體積、價(jià)值和數(shù)量。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0
<
N
,
V
≤
100
0<N,V≤100
0<N,V≤100
0
<
0<
0<v_i,w_i,s_i
≤
100
≤100
≤100
輸入樣例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
輸出樣例：
10
2. 思路分析
01背包：第
i
i
i 種物品可以取0件、取1件。
多重背包：第
i
i
i 種物品可以取0件、取1件、取2件…取
s
i
s_i
si?件。
多重背包問題轉(zhuǎn)化為01背包求解：把第
i
i
i 種物品換成
s
i
s_i
si? 件01背包中的物品，每件物品的體積為
k
?
v
i
k * v_i
k?vi?，價(jià)值為
k
?
w
i
k * w_i
k?wi?(0
≤
\leq
≤ k
≤
\leq
≤
s
i
s_i
si?)
3. 代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= m; j ++)
for (int k = 0; k <= s[i] && k * v[i] <= j; k ++)
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
cout << f[n][m] << endl;
return
}
四、多重背包問題 II
1. 題目描述
有 N 種物品和一個(gè)容量是 V 的背包。
第 i i i 種物品最多有 s i s_i si? 件，每件體積是 v i v_i vi?，價(jià)值是 w i w_i wi?。
求解將哪些物品裝入背包，可使物品體積總和不超過背包容量，且價(jià)值總和最大。
輸出最大價(jià)值。
輸入格式
第一行兩個(gè)整數(shù)，N，V，用空格隔開，分別表示物品種數(shù)和背包容積。
接下來有N 行，每行三個(gè)整數(shù) v i , w i , s i v_i,w_i,s_i vi?,wi?,si?，用空格隔開，分別表示第 i i i 種物品的體積、價(jià)值和數(shù)量。
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0
<
N
≤
1000
0<N≤1000
0<N≤1000
0
<
V
≤
2000
0<V≤2000
0<V≤2000
0
<
0<
0<v_i,w_i,s_i
≤
2000
≤2000
≤2000
提示：
本題考查多重背包的二進(jìn)制優(yōu)化方法。
輸入樣例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
輸出樣例：
10
2. 思路分析
二進(jìn)制優(yōu)化方法的例子：
假設(shè)有50個(gè)蘋果，現(xiàn)在要取
n
n
n 個(gè)蘋果（
n
n
n
≤
\leq
≤ 50），如何??？樸素的作家應(yīng)該是將蘋果一個(gè)一個(gè)拿出來，知道
n
n
n 個(gè)蘋果被取出來。
二進(jìn)制優(yōu)化的思想就是：再假設(shè)有5個(gè)蘋果和6只箱子，利用箱子繼續(xù)某些預(yù)備工作，可以在每個(gè)箱子中放 2 k 2^k 2k(k ≥ \geq ≥ 0)個(gè)蘋果，也就是1、2、4、8、16、19（剩余的數(shù)），取任意 n n n 個(gè)蘋果時(shí)，只需要推出幾只箱子就可以了。例如：取20個(gè)蘋果，只需要拿出2個(gè)箱子（1、19），這樣的話原來20次操作的現(xiàn)在變成2次操作就可以了。
二進(jìn)制拆分思想：
將第
i
i
i 種物品拆分成若干件物品，每件物品的體積和價(jià)值乘以一個(gè)拆分系數(shù)（1,
2
1
2^1
21,
2
2
2^2
22…
2
k
?
1
2^{k-1}
2k?1,
s
i
?
2
k
+
1
s_i - 2^k + 1
si??2k+1），就可以轉(zhuǎn)化成01背包的物品求解。
例如： s i = 12 s_i = 12 si?=12,拆分系數(shù)為 1 , 2 , 4 , 5 1,2,4,5 1,2,4,5，轉(zhuǎn)化成4件01背包的物品： ( v i , w i ) (v_i, w_i) (vi?,wi?)、 ( 2 v i , 2 w i ) (2v_i, 2w_i) (2vi?,2wi?)、 ( 4 v i , 4 w i ) (4v_i, 4w_i) (4vi?,4wi?)、 ( 5 v i , 5 w i ) (5v_i, 5w_i) (5vi?,5wi?)
3. 代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
using namespace std;
//逐一枚舉到最大是 N * logN
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N], f[M];
int main()
{
cin >> n >> m;
int cnt = 0; //分組的類別
for (int i = 1; i <= n; i ++)
{
int a, b, s;
cin >> a >> b >> s;
int k = 1; //組別里面的個(gè)數(shù)
while (k <= s)
{
cnt ++; //組別先增加
v[cnt] = a * k; //整體體積
w[cnt] = b * k; //整體價(jià)值
s -= k; //物品的個(gè)數(shù)要減少k個(gè)
k *= 2; //組別里面的個(gè)數(shù)增加
}
//剩余的一組
if (s >= 0)
{
cnt ++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt; //枚舉次數(shù)由個(gè)數(shù)變成組別數(shù)
//01背包一維優(yōu)化
for (int i = 1; i <= n; i ++)
for (int j = m; j >= v[i]; j --)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
五、分組背包問題
1. 題目描述
有 N 組物品和一個(gè)容量是 V 的背包。
每組物品有若干個(gè)，同一組內(nèi)的物品最多只能選一個(gè)。
每件物品的體積是
v
i
j
v_{ij}
vij?，價(jià)值是
w
i
j
w_{ij}
wij?，其中
i
i
i 是組號(hào)，
j
j
j 是組內(nèi)編號(hào)。
求解將哪些物品裝入背包，可使物品總體積不超過背包容量，且總價(jià)值最大。
輸出最大價(jià)值。
輸入格式
第一行有兩個(gè)整數(shù) N，V，用空格隔開，分別表示物品組數(shù)和背包容量。
接下來有 N 組數(shù)據(jù)：
- 每組數(shù)據(jù)第一行有一個(gè)整數(shù) S i S_i Si?，表示第 i i i 個(gè)物品組的物品數(shù)量；
- 每組數(shù)據(jù)接下來有 S i S_i Si? 行，每行有兩個(gè)整數(shù) v i j , w i j v_{ij},w_{ij} vij?,wij?，用空格隔開，分別表示第 i i i 個(gè)物品組的第 j j j 個(gè)物品的體積和價(jià)值；
輸出格式
輸出一個(gè)整數(shù)，表示最大價(jià)值。
數(shù)據(jù)范圍
0
<
N
,
V
≤
100
0<N,V≤100
0<N,V≤100
0
<
S
i
≤
100
0<S_i≤100
0<Si?≤100
$0<
v
i
j
,
w
i
j
v_{ij},w_{ij}
vij?,wij?≤100$
輸入樣例
3 5
2
1 2
2 4
1
3 4
1
4 5
輸出樣例：
8
2. 思路分析
最大價(jià)值應(yīng)該是物品組
i
i
i 和背包容量
j
j
j 的函數(shù)，用 f[i][j] 表示前
i
i
i 組物品，能放入容量為
j
j
j 的背包的最大價(jià)值。
樸素算法應(yīng)該是循環(huán)物品組，循環(huán)背包容量，對(duì)第 i i i 組物品，容量為 j j j 的背包，有 s + 1 s + 1 s+1 種選法，
max(f[i - 1][j], f[i - 1][j - v 1 v_1 v1?] + w 1 w_1 w1?, f[i - 1][j - v 2 v_2 v2?] + w 2 w_2 w2?,…,f[i - 1][j - v 5 v_5 v5?] + w 5 w_5 w5?)
代碼如下：
// 背包問題，樸素算法
for (int i = 1; i <= n; i ++) //物品
for (int j = 1; j <= m; j ++) //體積
for (int k = 0; k < s[i]; k ++) //決策
if (v[i][k] <= j)
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
cout << f[n][m] << endl;
可以優(yōu)化為一維數(shù)組：文章來源：http://www.zghlxwxcb.cn/news/detail-420805.html
for (int i = 1; i <= n; i ++) //物品
for (int j = m; j >= 0; j --) //體積
for (int k = 0; k < s[i]; k ++) //決策
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
3. 代碼實(shí)現(xiàn)
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> s[i];
for (int j = 0; j < s[i]; j ++)
cin >> v[i][j] >> w[i][j];
}
for (int i = 1; i <= n; i ++) //物品
for (int j = m; j >= 0; j --) //體積
for (int k = 0; k < s[i]; k ++) //決策
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}
創(chuàng)作不易，如果有幫助到你，請(qǐng)給文章點(diǎn)個(gè)贊和收藏，讓更多的人看到！??！
關(guān)注博主不迷路，內(nèi)容持續(xù)更新中。文章來源地址http://www.zghlxwxcb.cn/news/detail-420805.html
到了這里，關(guān)于算法基礎(chǔ)復(fù)盤筆記Day09【動(dòng)態(tài)規(guī)劃】—— 背包問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
