背包问题

本文默认 \(w_i\) 为重量，\(d_i\) 为价值，\(m_i\) 为数量

01背包

例题：P2871 [USACO07DEC] Charm Bracelet S

题目：

思路：

设 \(f_{i, j}\) 表示选到第 \(i\) 个物品，占用空间为 \(j\)可以获得的最大价值。

有 \(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - w[i]} + d[i])\)。

优化可得 \(f[j] = \max(f[j], f[j - w[i]] + d[i])\)。

注意：\(j\) 递归时一定要倒着来。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 3500, M = 13000;

int n, m;
int w[N], d[N];
int f[M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> w[i] >> d[i];
	
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= w[i]; j--) {
			f[j] = max(f[j], f[j - w[i]] + d[i]);
		}
	}
	cout << f[m] << '\n';
	return 0;
}

完全背包

例题：P1616 疯狂的采药

题目：

思路：

完全背包中物体可以被选无数次，而01背包每个物体只能选一次。

设 \(f_{i, j}\) 表示选到第 \(i\) 个物品，占用空间为 \(j\) 可以获得的最大价值。

有 \(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - w[i] \times k} + d[i] \times k)\)。

\(k\) 表示选取物体的数量。

优化可得 \(f[j] = \max(f[j], f[j - w[i]] + d[i])\)。

注意：\(j\) 递归时一定要正着来，与01背包相反。

代码：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 10010, M = 10000010;

int n, m;
int w[N], d[N];
i64 f[M];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> m >> n;
	for (int i = 1; i <= n; i++) cin >> w[i] >> d[i];
	
	for (int i = 1; i <= n; i++) {
		for (int j = w[i]; j <= m; j++) {
			f[j] = max(f[j], f[j - w[i]] + d[i]);
		}
	}
	cout << f[m] << '\n';
	return 0;
}

分组背包

例题：P1776 宝物筛选

题目：

思路：

完全背包中物体可以被选无数次，而分组背包每个物体有次数限制。

设 \(f_{i, j}\) 表示选到第 \(i\) 个物品，占用空间为 \(j\) 可以获得的最大价值。

有 \(f_{i, j} = \max(f_{i - 1, j}, f_{i - 1, j - w[i] \times k} + d[i] \times k)\)。

\(k\) 表示选取物体的数量，但其有次数限制。

二进制优化：

1. 如果物品 \(i\) 个数 \(m_i\) 乘以重量 \(w_i\)，那么该物品可以按照完全背包的做法来做；

2. 将次数 \(m_i\) 分成 \(1 + 2 + 4 + 2^n + k\)，那么 \(1\sim m_i\) 的每个数字都可以被表示出来，那么这些可以被看作一个个整体，可以按照01背包来做。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 110, W = 40010;

int n, g;
int f[W];
int v[N], w[N], m[N];

void solve() {
	for (int i = 1; i <= n; i++) {
		if (w[i] * m[i] >= g) {
			for (int j = w[i]; j <= g; j++) {
				f[j] = max(f[j], f[j - w[i]] + v[i]);
			}
		}
		else {
			for (int k = 1; m[i]; k <<= 1) {
				int use = min(k, m[i]);
				for (int j = g; j >= w[i] * use; j--) {
					f[j] = max(f[j], f[j - w[i] * use] + v[i] * use);
				}
				m[i] -= use;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> g;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> m[i];
	solve();
	
	cout << f[g] << '\n';
	return 0;
}

分组背包

例题：P1757 通天之分组背包

题目：

思路：

对组里的每一个物体按照01背包的方式处理，

注意三层循环的顺序，

否则有可能会多选。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 1010;

int n, m, s;
int f[M];
int a[N][N], b[N][N], cnt[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        s = max(s, z);
        cnt[z]++;
        a[z][cnt[z]] = x, b[z][cnt[z]] = y;
    }

    for (int i = 1; i <= s; i++) {
        for (int k = m; k >= 0; k--) {
            for (int j = 1; j <= cnt[i]; j++) {
                if (k < a[i][j]) continue;
                f[k] = max(f[k], f[k - a[i][j]] + b[i][j]);
            }
        }
    }

    cout << f[m] << '\n';
    return 0;
}

有依赖的背包

参见我的博客。