「學習筆記」DP學習筆記 3
背包DP
0-1背包
給你 \(n\) 個物品和一個容量為 \(W\) 的背包，每個物品有自己的價值 \(v\) 和 需要占用的空間 \(c\)，求背包中的物品的所占用的空間不超過容量的最大價值。
特點：每個物品只能選一次。
設置狀態：\(f(i, j)\) 意味著前 \(i\) 個物品，容量為 \(j\) 的最大價值。
對于第 \(i\) 個物品，有選和不選兩種情況，由此可以得到狀態轉移方程：
\[f(i, j) = \max \{ f(i - 1, j), f(i - 1, j - c_i) + w_i \}
\]
由于二維空間有時會 MLE，同時我們發現對于 \(f_i\)，只有 \(f_{i - 1}\) 會對它有貢獻，因此我們可以使用滾動數組優化，將狀態轉移方程優化為：
\[f_j = \max \{ f_j, f_{j - c_i} + w_i \}
\]
寫成該轉移方程式，則枚舉容量要從大到小枚舉，因為在 \(f_j\) 更新時，\(f_{j - c_i}\) 是不能被更新的，以免將 \(f(i - 1, j - c_i)\) 的信息覆蓋掉。
例題：
[NOIP2005 普及組] 采藥
山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。在給定的時間里，你要讓采到的草藥的總價值最大。
0-1 背包的模板題，很適合入門。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 110;
int W, n;
int c[N], v[N], f[1010];
int main() {
W = read<int>(), n = read<int>();
for (int i = 1; i <= n; ++ i) {
c[i] = read<int>(), v[i] = read<int>();
}
for (int i = 1; i <= n; ++ i) {
for (int j = W; j >= c[i]; -- j) {
f[j] = max(f[j], f[j - c[i]] + v[i]);
}
}
printf("%d\n", f[W]);
return 0;
}
完全背包
與 0-1 背包類似，但不同的地方在于，0-1 背包中每種物品只能選一次，而完全背包中每種物品可以選無數次。
設置狀態：\(f(i, j)\) 意味著前 \(i\) 個物品，容量為 \(j\) 的最大價值。
轉移方程如下：
\[f(i, j) = \max_{k = 0}^{+\infty} \{ f(i - 1, j), f(i - 1, j - k \times c_i) + v_i \times k \}
\]
我們做一個簡單的優化，對于 \(f(i, j)\)，只要通過 \(f(i, j - c_i)\) 轉移就行了，因此轉移方程為：
\[f(i, j) = \max \{ f(i - 1, j), f(i, j - c_i) + v_i \}
\]
為什么是對的呢，我們可以這樣想，\(f(i, j - c_i)\) 已經由 \(f(i, j - 2 \times c_i)\) 更新過了，所以 \(f(i, j - c_i)\) 肯定是考慮了第 \(i\) 件物品的選擇次數和空間的最優結果了，相當于最優子結構，我們可以利用局部最優子結構來優化枚舉的復雜度。
同樣，完全背包也可以將狀態從二維化簡為一維，轉移方程式如下：
\[f_j = \max\{ f_j, f_{j - c_i} + v_i \}
\]
枚舉順序為正序枚舉。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 1e4 + 5;
const int M = 1e7 + 5;
int t, n;
int a[N], b[N];
ll f[M];
int main() {
t = read<int>(), n = read<int>();
for (int i = 1; i <= n; ++ i) {
a[i] = read<int>(), b[i] = read<int>();
}
for (int i = 1; i <= n; ++ i) {
for (int j = a[i]; j <= t; ++ j) {
f[j] = max(f[j], f[j - a[i]] + b[i]);
}
}
printf("%lld\n", f[t]);
return 0;
}
多重背包
與 0-1 背包的不同在于每個物品有 \(k\) 個。
\[f(i, j) = \max_{k = 0}^{k_i} \{ f(i - 1, j - k \times c_i) + v_i \times k \}
\]
優化：二進制拆分
可以使用二進制分組來時拆分方式更優美。
代碼來自 \(\texttt{OI-Wiki}\)。
index = 0;
for (int i = 1; i <= m; i++) {
int c = 1, p, h, k;
cin >> p >> h >> k;
while (k > c) {
k -= c;
list[++index].w = c * p;
list[index].v = c * h;
c *= 2;
}
list[++index].w = p * k;
list[index].v = h * k;
}
混合背包
混合背包就是前三種背包混合在一起，即有些物品只能取一次，有些能取無數次，有些能取 \(k\) 次。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 1e4 + 5;
using tii = tuple<int, int>;
int n, t;
int c[N], v[N], p[N];
ll f[N];
char s[N];
int main() {
int begh, begm, endh, endm;
scanf("%s", s);
sscanf(s, "%d:%d", &begh, &begm);
scanf("%s", s);
sscanf(s, "%d:%d", &endh, &endm);
t = (endm - begm + 60) % 60;
if (endm < begm) {
t += (endh - begh - 1) * 60;
} else {
t += (endh - begh) * 60;
}
n = read<int>();
for (int i = 1; i <= n; ++ i) {
c[i] = read<int>(), v[i] = read<int>(), p[i] = read<int>();
}
for (int i = 1; i <= n; ++ i) {
if (p[i] == 1) {
for (int j = t; j >= c[i]; -- j) {
f[j] = max(f[j], f[j - c[i]] + v[i]);
}
} else if (p[i] == 0) {
for (int j = c[i]; j <= t; ++ j) {
f[j] = max(f[j], f[j - c[i]] + v[i]);
}
} else {
vector<tii> tmp;
for (int g = 1; p[i] > g; g <<= 1) {
p[i] -= g;
tmp.emplace_back(g * c[i], g * v[i]);
}
if (p[i]) {
tmp.emplace_back(p[i] * c[i], p[i] * v[i]);
}
int C, V;
for (tii it : tmp) {
tie(C, V) = it;
for (int j = t; j >= C; -- j) {
f[j] = max(f[j], f[j - C] + V);
}
}
}
}
printf("%lld\n", f[t]);
return 0;
}
二維費用背包
與 0-1 背包相比，二維費用背包在選擇物品時還要考慮費用，只需要在多一層循環來枚舉費用即可，這里再開一維空間來存放物品編號就很容易 MLE 了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 110;
int n, m, t;
int mo[N], ti[N];
ll f[N << 1][N << 1];
int main() {
n = read<int>(), m = read<int>(), t = read<int>();
for (int i = 1; i <= n; ++ i) {
mo[i] = read<int>(), ti[i] = read<int>();
}
for (int i = 1; i <= n; ++ i) {
for (int j = m; j >= mo[i]; -- j) {
for (int k = t; k >= ti[i]; -- k) {
f[j][k] = max(f[j][k], f[j - mo[i]][k - ti[i]] + 1);
}
}
}
printf("%lld\n", f[m][t]);
return 0;
}
分組背包
與 0-1 背包相比，就是在當前組中只能選擇一個，然后求最大價值。
對每一組都進行 0-1 背包即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 1100;
using tii = tuple<int, int>;
int n, m, lim;
ll f[N];
vector<tii> g[N];
int main() {
m = read<int>(), n = read<int>();
for (int i = 1, a, b, c; i <= n; ++ i) {
a = read<int>(), b = read<int>(), c = read<int>();
g[c].emplace_back(a, b);
lim = max(lim, c);
}
for (int i = 1; i <= lim; ++ i) {
for (int j = m; j >= 0; -- j) {
for (tii it : g[i]) {
if (j >= get<0>(it)) {
f[j] = max(f[j], f[j - get<0>(it)] + get<1>(it));
}
}
}
}
printf("%lld\n", f[m]);
return 0;
}
有依賴的背包
將主件與復件分類討論，變化成分組背包即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? -x : x;
}
const int N = 5e4 + 5;
using tii = tuple<int, int>;
int n, m;
ll sumv, sump;
ll v[N], p[N], q[N];
ll f[N];
vector<tii> s[N], z[N];
void dfs(int i, int u) {
if (u == (int)s[i].size()) {
z[i].emplace_back(v[i] + sumv, p[i] * v[i] + sump);
return ;
}
sumv += get<0>(s[i][u]);
sump += get<1>(s[i][u]) * get<0>(s[i][u]);
dfs(i, u + 1);
sumv -= get<0>(s[i][u]);
sump -= get<1>(s[i][u]) * get<0>(s[i][u]);
dfs(i, u + 1);
}
int main() {
n = read<int>(), m = read<int>();
for (int i = 1; i <= m; ++ i) {
v[i] = read<int>(), p[i] = read<int>(), q[i] = read<int>();
s[q[i]].emplace_back(v[i], p[i]);
}
for (int i = 1; i <= m; ++ i) {
if (q[i] == 0) {
dfs(i, 0);
}
}
for (int i = 1; i <= m; ++ i) {
for (int j = n; j >= 0; -- j) {
int V, P;
for (tii it : z[i]) {
tie(V, P) = it;
if (V <= j) {
f[j] = max(f[j], f[j - V] + P);
}
}
}
}
printf("%lld\n", f[n]);
return 0;
}
朝氣蓬勃 后生可畏
浙公網安備 33010602011771號