背包问题

背包问题九讲 2.0 by 崔添翼 (dd_engi) 现在才把这篇文章完整地看了一遍......再不看就得等到明年了...... 本文是学习笔记及原文的扩充. # 记号 n个物品, 总容量为m, 价值为w, 体积为v, 数量限制为c. 最大化价值.

设前i个物品, 背包容量为j, 最大价值为f(i,j). 有时省去第一维, 以f,f'代之.

01 背包和完全背包

void init(int* f, bool t)
{
	if (b) // 总体积恰好为 m
		fill_n(f+1, m, -inf), f[0] = 0;
	else // 总体积不超过 m
		fill_n(f, m+1, 0);
}
void zero_one_pack(int* f, int v, int w)
{
	per (i, m, v)
		f[i] = max(f[i], f[i-v] + w);
}
void complete_pack(int* f, int v, int w)
{
	rep (i, v, m+1)
		f[i] = max(f[i], f[i-v] + w);
}

多重背包

二进制拆分

按二进制拆成 O(lg c) 个物品, 跑 01 背包.

单调队列

每个模v的剩余系分别处理, 设现在处理i. 令g(j) = f((j-1)v + i).

g'(j) = max { g(k) - kw | max(i-m,0) <= k <= j } + jw

单调队列优化.

void multiple_pack(int* f, int v, int w, int c)
{
	static ii Q[M+1];
	rep (i, 0, v)
	{
		ii* p = Q, * q = Q-1;
		for (int j = 1, k = i; k <= m; ++j, k += v)
		{
			ii x(f[k] - j*w, j);
			while (q-p >= 0 && x.first > q->first) --q;
			*++q = x;
			p += j - p->second > c;
			f[k] = p->first + j*w;
		}
	}
}

泛化物品

一个物品可以看作一个函数, 输出体积, 返回价值. 求解背包问题可以看作对泛化物品求和:

void merge_pack(int* f, int a, int* g, int b)
{
	per (i, min(m, a+b), 0)
	{
		f[i] = max(-inf, f[i] + g[0]);
		rep (j, max(0, i-s), i)
			f[i] = max(f[i], f[j] + g[i-j]);
	}
}

树形依赖背包

依赖关系形成一棵树. 一个物品选了, 它的祖先也得选.

本文这部分来自6月雅礼集训 myy 的讲课.

泛化物品求和

void tree_pack_naive(int f[N][M], int x)
{
	fill_n(f[x], m+1, -inf);
	f[v[x]] = w[x];
	sum[x] = v[x];
	for (auto y : adj[x])
	{
		tree_pack_naive(f, y);
		merge_pack(f[x], s, f[y], sum[y]);
		sum[x] += sum[y];
	}
	f[0] = 0;
}

时间复杂度 O(nm^2).

所有物品体积为1

合并f[x]和所有f[y]的代价与 lca(u,v)=x 的 (u,v) 的数目同阶. 故总时间复杂度为 O(n^2).

DFS序

设seq为前序遍历得到的序列, size为子树大小.

void tree_pack_dfs_seq(int f[N+1][M+1], int n)
{
	init(f[n], 0);
	per (i, n-1, 0) rep (j, 0, m+1)
		f[i][j]
		= max(f[i + size[seq[i]]][j], f[i+1][j-v[seq[i]]] + w[seq[i]]);
	// result = f[0]
}

K 优解

用一个队列维护每个状态的 K 优解, 则取 max 操作转化为两个队列的合并, 取前 K 项.

以 01 背包为例. max(f[i], f[i-v] + w) 是 f[i], f[i-v]每个元素 + w, 这两个队列的合并.