洛谷 P1064 金明的预算方案 有依赖的背包问题

缘起

这也算是一道著名的NOIP题目了~ 洛谷 P1064 金明的预算方案

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
本题是NOIP2006提高组的第二题
题目描述
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的
是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。
今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，
下表就是一些主件与附件的例子：

主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自
己的附件。金明想买的东西很多，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用
整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是10元的整数倍）。他希望在不超过N元
（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1，j2，……，jk，则所求的总和为：
v[j1]*w[j1]+v[j2]*w[j2]+...+v[jk]*w[jk]。（其中*为乘号）请你帮助金明设计一个满足要求的购物单。

输入格式
输入文件的第1行，为两个正整数，用一个空格隔开：N m 其中N（<32000）表示总钱数，m（<60）为希望购买物品
的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q（其中v表示
该物品的价格（v<10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品
为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

样例输入
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

样例输出
2200

因为题目说的很明白了”每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。”
所以首先将所有物品扫一遍,将所有主件以及它的附件组合成一个物品,这个物品有5种取拿策略

  1. 完全不取
  2. 只取主件
  3. 取主件+附件1
  4. 取主件+附件2
  5. 取主件+附件1+附件2

所以可以将原问题转换为分组背包的问题解决,dp模型是

1
2
3
4
5
6
7
8
9
10
f[i][j]=max{
f[i-1][j], // 完全不取
f[i-1][j-a[i][0]]+a[i][0]*b[i][0], // 只取主件
f[i-1][j-a[i][0]-a[i][1]]+a[i][0]*b[i][0]+a[i][1]*b[i][1], // 取主件+附件1
f[i-1][j-a[i][0]-a[i][2]]+a[i][0]*b[i][0]+a[i][2]*b[i][2], // 取主件+附件2
f[i-1][j-a[i][0]-a[i][1]-a[i][2]]+a[i][0]*b[i][0]+a[i][1]*b[i][1]+a[i][2]*b[i][2] // 取主件+附件1+附件2
}

其中f[i][j]是只考虑前i组物品的取舍的时候用j元钱(注意，本题的耗费是钱的数量)能够达到的价值*重要度
的最大值

当然可以用滚动数组优化空间复杂度. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 65,maxv = 32005;
int n,m, vv[maxn], p[maxn], q[maxn], dp[maxv],cnt; // cnt是物品组的个数, dp[i][j]是取前i个物品组容量为j的时候最大价值,但是我们将i滚动掉了
bool sz[maxn]; // true 表示是主件, 否则是附件
vector<int> g[maxn]; // g[i]表示以物品i为主件的物品组

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	for (int i = 1;i<=m;i++)
	{
		scanf("%d%d%d", vv+i, p+i,q+i);
		if (q[i])
		{
			g[q[i]].push_back(i); // 物品i以q[i]为主件
		}
		else
		{
			sz[i] = true;
		}
	}
	for (int k = 1;k<=m;k++) // 施展分组背包
	{
		if (!sz[k])
		{
			continue;
		} // 直至选到了一个组, 这个组是以 k 物品为主件, g[k]中的元素为其附件, 其中g[k]的长度<=2(即不超过2件附件)
		for (int v = n,len,one,two; ~v; v--)
		{
			len = g[k].size(); // 枚举分组中的每件物品(其实对于本题而言, 分组中的物品根本不是一件一件的物品,而是选取物品的策略, 至多5种策略,所以每组物品中最多5件物品, 他们是互斥的)
			if (v>=vv[k]) // 和【1】一样
			{
				dp[v] = max(dp[v], dp[v-vv[k]]+vv[k]*p[k]);
			}
			if (len>=1)
			{
				one = g[k][0]; // 第一件附件编号
				if (v>=vv[k]+vv[one]) // 选择主件和第一件附件
				{
					dp[v] = max(dp[v], dp[v-vv[k]-vv[one]]+vv[k]*p[k]+vv[one]*p[one]);
				}
			}
			if (len>=2)
			{
				two = g[k][1]; // 第二件附件的编号
				if (v>=vv[k]+vv[two]) // 选择主件和第二件附件
				{
					dp[v] = max(dp[v], dp[v-vv[k]-vv[two]]+vv[k]*p[k]+vv[two]*p[two]);
				}
				if (v>=vv[k]+vv[one]+vv[two]) // 选择主件、第一件附件和第二件附件
				{
					dp[v] = max(dp[v], dp[v-vv[k]-vv[one] - vv[two]]+vv[k]*p[k]+vv[one]*p[one]+vv[two]*p[two]);
				}
			}
		}
	}
	printf("%d", dp[n]);
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P1064 金明的预算方案
评测状态
Accepted
评测分数
100

后续的讨论

以下讨论源自崔天翼神犇（or2）的《背包九讲2.0》的第七章和第八章.

其实本题是有依赖的背包问题. 所谓有依赖的背包问题是

1
2
这种背包问题的物品之间存在某种依赖关系, 也就是说, 物品i依赖物品j,表示若选择物品i, 则必须选取物品j
换言之, 可以将物品j理解为本题的主件, 物品i理解为附件.

为简单起见, 我们先假设没有一个物品既依赖别的物品，也被别的物品所依赖（即树的高度不会>2）. 而且没有某件物品同时依赖多件物品（即不会两个主件有同一个附件这种情况发生）. 即物品的依赖关系是下面这个样子的

​ 图1

在这种假设下, 假设一个主件至多有n件附件（本题n=2）, 则如果依旧使用本题的算法的话（本题其实是暴力枚举了所有的选取策略，即暴力枚举了分组中的所有2^n+1件物品（就像上面代码所说, 分组中的物品其实是选择物品的策略，这里+1其实是一件物品都不选这种选择策略）,然后跑分组背包），则复杂度将是 2^n*组数*背包容量V， 这是一个不小的复杂度. 本题之所以能过是因为n 较小. n一旦大起来, 则这个暴力算法岌岌可危~ 怎么优化呢? 我们观察一下这2^n+1 件物品（再说一遍, 分组中的物品其实是选择策略）, 很多种物品的耗费其实是一样的, 所以我们完全可以使用完全背包中的优化(参见《背包九讲2.0》2.3节)——只保留性价比最高的, 即只需要计算出容量为v时（ci<=v<=V, >=ci是因为主件必须选，ci是主件的价值） 的最大价值, 将这2^n+1种选择策略只保留

实现v（ci<=v<=V）容量下的最大价值 这 V-ci+1 件物品（选择策略）即可. 注意, 这V-ci+1件物品其实是一个函数啊（这个观点对于后面讨论的泛化物品相当重要! 后面你就会知道，一个物品组就是一个泛化物品~）~

其中F[v]就是这个主件以及它的一堆附件在容量v的限制下的最大值.

而怎么能计算出容量为v下的最大价值呢? 显然只需要对这n件附件（为什么不包含主件?因为主件必须下选）跑一遍01背包就行了, 就能知道v容量下（0<=v<=V-ci）的最大价值.加上ci（因为主件必须选）就是F[v]了 所以在 V较小, 而n较大的情况下这种算法会提升很多性能. 因为2^n远大于 V, 这2^n件物品（选择策略）很多是耗费一样，但是价值不一样的, 我们的优化算法仅仅保留同等耗费下，价值最大的那个选择策略即可. 这能有效降低分组中物品（其实就是物品选择策略）的个数.

避开上面的函数，既然我们已经将每个主件以及它的附件的2^n+1种选择策略转换为一个物品组, 并且在n较大的时候将物品组中物品数量由2^n缩减为V-ci+1（注意，关于这个+1啊~ 就是该物品组不选任何一个物品这种策略， 其实在跑分组背包的时候, dp[v] = max(dp[v],dp[v-Ci]+Wi), max里面的dp[v]其实就是这种选择策略啊~ 所以其实不必特别拿出来讨论的）, 我们就可以针对 K个物品组（第i个物品组有V-ci+1件物品）跑分组背包就行了.从而解决了这个问题.

上面的讨论我们限定了树的深度不能>2, 如果打开这一限制——即物品的依赖关系是以一般森林给出的. 即只保留每个物品最多只依赖一件主件 这一限制的话, 有依赖的背包问题怎么解决呢?

首先, 物品依赖关系变成下面的样子

​ 图2

X是主件, 下面的都是X的附件. 当然, 题目的数据可能有很多X（所以才说是森林嘛，即多叉树的集合~）, 则此情此景，如何解决有依赖的背包问题呢? 解决这个问题仍然可以用将每个主件及其附件的选择策略集合视作物品组的方式转换为分组背包。但是由于附件可能还有附件（即树的深度可能>2），就不能将每个附件都看作一个一般的01背包中的物品了。 而要将A、B、C视作上面提到的函数. 所谓函数就是你给它多少容量. 它就返给你（此容量下）的最优解. 所以上面的问题本质上就是将每个节点都视作一个函数的树形dp问题.（其实对于图1的情形又何尝不是这样呢?）.

上面依赖树上每个节点都可以视作一个定义域为[0,V]的, 且在[0,c]（c是该节点的价值）恒为0的函数。

而这个函数其实就是崔天翼《背包九讲2.0》的第八章提到的泛化物品~ 每个依赖树的节点其实都是一个泛化物品~

为什么叫做泛化物品? 因为它的价值不是固定的（当然，依赖树的叶子节点作为泛化物品价值是固定的，它是特殊的泛化物品~）, 而是依赖于你分配给它的容量限制v是多少, 它的价值就是f(v). 求某个节点对应的泛化物品（即函数）其实就是它的子节点作为泛化物品（即函数）的和（即函数的和，其实确切讲, 假设有k个子节点， 则

f[v] = max{f1[v1]+f2[v2]+…+fk[vk]， 其中v1+v2+…+vk=v}）

而两个泛化物品的和依旧是一个泛化物品~ 就像《背包九讲2.0》第八章的那个公式一样

f(v) = max { h(k) + l(v - k) j 0 ≤ k ≤ v} 就是泛化物品h和泛化物品l的和为f的刻画.

而多个物品求和的结果自然也是泛化物品, 怎么求这个泛化物品呢? 或者说代码怎么实现多个泛化物品求和呢? 其实跑一遍分组背包, 最后的滚动数组dp[0,…,V] 就是这些泛化物品的和，即一个新的泛化物品了~

参考

【1】https://yfsyfs.github.io/2019/10/25/hdu-1712-ACboy-needs-your-help-%E5%88%86%E7%BB%84%E8%83%8C%E5%8C%85/