nbhkdz.com冰点文库

背包九讲

时间:2010-08-28


P01: 01 背包问题 题目 的背包。 有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i], w[i]。 c[i],价值是 w[i]。求解将哪些物品装入背包可使这些物品 的费用总和不超过背包容量,且价值总和最大。 的费用总和不超过背包容量,且价值总和最大。

基本思路 这是最基础的背包问题,特点是:每种物品仅有一件, 这是最基础的背包问

题,特点是:每种物品仅有一件,可以 选择放或不放。 选择放或不放。

用子问题定义状态: f[i][v]表示前 用子问题定义状态:即 f[i][v]表示前 i 件物品恰放入一个 的背包可以获得的最大价值。 容量为 v 的背包可以获得的最大价值。则其状态转移方程便 是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

这个方程非常重要,基本上所有跟背包相关的问题的方程都 这个方程非常重要,基本上所有跟背包相关的问题的方程都 是由它衍生出来的。 “ 是由它衍生出来的。所以有必要将它详细解释一下: 将前 i 所以有必要将它详细解释一下: 的背包中”这个子问题, 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放) ,那么就可以转化为一个只牵扯 件物品的策略(放或不放) 那么就可以转化为一个只牵扯 , 件物品的问题。 件物品, 前 i-1 件物品的问题。如果不放第 i 件物品,那么问题就转 化为“ 的背包中” 化为“前 i-1 件物品放入容量为 v 的背包中” 如果放第 i ; 件物品,那么问题就转化为“ 件物品,那么问题就转化为“前 i-1 件物品放入剩下的容量 为 v-c[i] 的 背 包 中 ” 此 时 能 获 得 的 最 大 价 值 就 是 f ,

[i-1][v[i-1][v-c[i]] 再 加 上 通 过 放 入 第 i 件 物 品 获 得 的 价 值 w[i]。 w[i]。

f[i][v]有意义当且仅当存在一个 有意义当且仅当存在一个前 件物品的子集, 注意 f[i][v]有意义当且仅当存在一个前 i 件物品的子集, 所以按照这个方程递推完毕后, 其费用总和为 v。所以按照这个方程递推完毕后,最终的答 [V], f[N][0..V]的最大值 的最大值。 案并不一定是 f[N] [V],而是 f[N][0..V]的最大值。如果 将状态的定义中的“ 将状态的定义中的“恰”字去掉,在转移方程中就要再加入 字去掉, f[i][v-1], [V]就是最后的答案 就是最后的答案。 一项 f[i][v-1], 这样就可以保证 f[N] [V]就是最后的答案。 至于为什么这样就可以,由你自己来体会了。 至于为什么这样就可以,由你自己来体会了。

优化空间复杂度 O(N*V), 以上方法的时间和空间复杂度均为 O(N*V), 其中时间复杂度 基本已经不能再优化了, O(V)。 基本已经不能再优化了,但空间复杂度却可以优化到 O(V)。

先考虑上面讲的基本思路如何实现, 先考虑上面讲的基本思路如何实现 , 肯定是有一个主循环 i=1..N,每次算出来二维数组 f[i][0..V]的所有值 那么, 的所有值。 i=1..N,每次算出来二维数组 f[i][0..V]的所有值。那么, [0..V], 如果只用一个数组 f [0..V],能不能保证第 i 次循环结束后 f[v]中表示的就是我们定义的状态 f[i][v]呢 f[i][v]是 f[v]中表示的就是我们定义的状态 f[i][v]呢? f[i][v]是 f[i-1][v]和 f[i[v-c[i]]两个子问题递推而来 两个子问题递推而来, 由 f[i-1][v]和 f[i-1] [v-c[i]]两个子问题递推而来,能 f[i][v]时 f[v]时 否保证在推 f[i][v]时(也即在第 i 次主循环中推 f[v]时) f[i-1][v]和 f[ic[i]]的值呢 事实上, 的值呢? 能够得到 f[i-1][v]和 f[i-1][v -c[i]]的值呢?事实上, f[v], 这要求在每次主循环中我们以 v=V..0 的顺序推 f[v],这样

f[v]时 f[v-c[i]]保存的是状态 1][v [v才能保证推 f[v]时 f[v-c[i]]保存的是状态 f[i -1][v-c[i]] 的值。伪代码如下: 的值。伪代码如下:

for i=1..N for v=V..0 f[v]=max{f[v],f[vf[v]=max{f[v],f[v-c[i]]+w[i]};

f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的 其中的 f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的 f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}, 转移方程 f[i][v]=max{f[i-1][v],f[i- 1][v-c[i]]}, 因为 f[v-c[i]]就相当于原来的 f[i-1][v-c[i]]。 现在的 f[v-c[i]]就相当于原来的 f[i-1][v-c[i]]。如果将 的循环顺序从上面的逆序改成顺序的话, v 的循环顺序从上面的逆序改成顺序的话 , 那么则成了 f[i][v]由 f[i][v-c[i]]推知 与本题意不符, 推知, f[i][v]由 f[i][v-c[i]]推知,与本题意不符,但它却是另 最简捷的解决方案, 一个重要的背包问题 P02 最简捷的解决方案,故学习只用一 背包问题是十分必要的。 维数组解 01 背包问题是十分必要的。

总结 背包问题是最基本的背包问题, 01 背包问题是最基本的背包问题, 它包含了背包问题中设计 状态、方程的最基本思想,另外, 状态、方程的最基本思想,另外,别的类型的背包问题往往 背包问题求解。 也可以转换成 01 背包问题求解。故一定要仔细体会上面基 本思路的得出方法,状态转移方程的意义, 本思路的得出方法,状态转移方程的意义,以及最后怎样优 化的空间复杂度。 化的空间复杂度。

P02: 完全背包问题 题目 的背包, 有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可 c[i], w[i]。 用。第 i 种物品的费用是 c[i],价值是 w[i]。求解将哪些 物品装入背包可使这些物品的费用总和不超过背包容量, 物品装入背包可使这些物品的费用总和不超过背包容量,且 超过背包容量 价值总和最大。 价值总和最大。

基本思路 背包问题, 这个问题非常类似于 01 背包问题,所不同的是每种物品有 无限件。也就是从每种物品的角度考虑, 无限件。也就是从每种物品的角度考虑,与它相关的策略已 并非取或不取两种, ……等 并非取或不取两种,而是有取 0 件、取 1 件、取 2 件……等 很多种。 如果仍然按照解 01 背包时的思路, f[i][v]表示 背包时的思路, f[i][v]表示 很多种。 令 的背包的最大权值。 前 i 种物品恰放入一个容量为 v 的背包的最大权值。仍然可 以按照每种物品不同的策略写出状态转移方程,像这样: 以按照每种物品不同的策略写出状态转移方程 , 像这样 : f[i][v]=max{f[i-1][vv}。 f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<= v}。 O(N*V)个状态需要求解, 个状态需要求解 这跟 01 背包问题一样有 O(N*V)个状态需要求解,但求解每 个状态的时间则不是常数了, f[i][v]的时间是 个状态的时间则不是常数了 , 求解状态 f[i][v] 的时间是 O(v/c[i]), O(VN)的 O(v/c[i]),总的复杂度是超过 O(VN)的。

背包问题的基本思路加以改进, 将 01 背包问题的基本思路加以改进,得到了这样一个清晰 的方法。 背包问题的方程的确是很重要, 的方法。这说明 01 背包问题的方程的确是很重要,可以推 及其它类型的背包问题。但我们还是试图改进这个复杂度。 及其它类型的背包问题。但我们还是试图改进这个复杂度。

一个简单有效的优化 完全背包问题有一个很简单有效的优化,是这样的: 完全背包问题有一个很简单有效的优化,是这样的:若两件 c[i]<=c[j]且 w[i]>=w[j], 去掉, 物品 i、 满足 c[i]<=c[j]且 w[i]>=w[j], j 则将物品 j 去掉, 不用考虑。这个优化的正确性显然: 不用考虑。这个优化的正确性显然:任何情况下都可将价值 换成物美价廉的 得到至少不会更差的方案。 得到至少不会更差的方案。 小费用高得 j 换成物美价廉的 i, 对于随机生成的数据, 对于随机生成的数据 , 这个方法往往会大大减少物品的件 从而加快速度。 然而这个并不能改善最坏情况的复杂度, 数, 从而加快速度。 然而这个并不能改善最坏情况的复杂度, 因为有可能特别设计的数据可以一件物品也去不掉。 因为有可能特别设计的数据可以一件物品也去不掉。

转化为 01 背包问题求解 背包问题是最基本的背包问题, 既然 01 背包问题是最基本的背包问题,那么我们可以考虑 背包问题来解。最简单的想法是, 把完全背包问题转化为 01 背包问题来解。最简单的想法是, [i]件 考虑到第 i 种物品最多选 V/c [i]件,于是可以把第 i 种物 V/c[i]件费用及价值均不变的物品 然后求解这个 件费用及价值均不变的物品, 品转化为 V/c[i]件费用及价值均不变的物品, 背包问题。 这样完全没有改进基本思路的时间复杂度, 01 背包问题。这样完全没有改进基本思路的时间复杂度,但 这毕竟给了我们将完全背包问题转化为 背包问题的思路: 这毕竟给了我们将完全背包问题转化为 01 背包问题的思路: 将一种物品拆成多件物品。 将一种物品拆成多件物品。

更高效的转化方法是: c[i]*2^k、 更高效的转化方法是:把第 i 种物品拆成费用为 c[i]*2^k、 的若干件物品, c[i]*2^k<V。 价值为 w[i]*2^k 的若干件物品,其中 k 满足 c[i]*2^k<V。 这是二进制的思想, 种物品, 这是二进制的思想,因为不管最优策略选几件第 i 种物品,

件物品的和。 总可以表示成若干个 2^k 件物品的和。这样把每种物品拆成 O(log(V/c[i]))件物品,是一个很大的改进。 O(log(V/c[i]))件物品,是一个很大的改进。 但我们有更 件物品 O(VN)的算法 的算法。 O(VN)的算法 优的 O(VN)的算法。 * O(VN)的算法 这个算法使用一维数 组,先看伪代码: <pre class"example"> for i=1..N for 先看伪代码: f[v]=max{f[v],f[vv=0..V f[v]=max{f[v],f[v-c[i]]+w[i]};

你会发现, 你会发现,这个伪代码与 P01 的伪代码只有 v 的循环次序不 同而已。为什么这样一改就可行呢? 同而已。为什么这样一改就可行呢?首先想想为什么 P01 中 的逆序来循环。 要按照 v=V..0 的逆序来循环。这是因为要保证第 i 次循环 f[i][v]是由状态 f[i-1][v-c[i]]递推而来 递推而来。 中的状态 f[i][v]是由状态 f[i-1][v-c[i]]递推而来。换句 话说,这正是为了保证每件物品只选一次,保证在考虑“ 话说,这正是为了保证每件物品只选一次,保证在考虑“选 件物品”这件策略时, 入第 i 件物品”这件策略时,依据的是一个绝无已经选入第 f[i-1][v-c[i]]。 i 件物品的子结果 f[i-1][v-c[i]]。而现在完全背包的特点 恰是每种物品可选无限件 所以在考虑“ 恰是每种物品可选无限件,所以在考虑“加选一件第 i 种物 品”这种策略时,却正需要一个可能已选入第 i 种物品的子 这种策略时, f[i][v-c[i]], 结果 f[i][v-c[i]],所以就可以并且必须采用 v= 0..V 的顺 序循环。这就是这个简单的程序为何成立的道理。 序循环。这就是这个简单的程序为何成立的道理。

这个算法也可以以另外的思路得出。例如, 这个算法也可以以另外的思路得出。例如,基本思路中的状 态 转 移 方 程 可 以 等 价 地 变 形 成 这 种 形 式 :

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}, 将这个方程 f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}, 用一维数组实现,便得到了上面的伪代码。 用一维数组实现,便得到了上面的伪代码。

总结 完全背包问题也是一个相当基础的背包问题, 完全背包问题也是一个相当基础的背包问题,它有两个状态 转移方程,分别在“基本思路 以及“O(VN)的算法 的算法“ 转移方程,分别在“基本思路”以及“O(VN)的算法“的小 节中给出。 节中给出 。 希望你能够对这两个状态转移方程都仔细地体 会,不仅记住,也要弄明白它们是怎么得出来的,最好能够 不仅记住,也要弄明白它们是怎么得出来的, 自己想一种得到这些方程的方法。事实上, 自己想一种得到这些方程的方法。事实上,对每一道动态规 划题目都思考其方程的意义以及如何得来, 划题目都思考其方程的意义以及如何得来,是加深对动态规 划的理解、提高动态规划功力的好方法。 划的理解、提高动态规划功力的好方法。

P03: 多重背包问题 题目 的背包。 有 N 种物品和一个容量为 V 的背包。 i 种物品最多有 n[i] 第 件可用, c[i], w[i]。 件可用,每件费用是 c[i],价值是 w[i]。求解将哪些物品 装入背包可使这些物品的费用总和不超过背包容量, 装入背包可使这些物品的费用总和不超过背包容量,且价值 总和最大。 总和最大。

基本算法 这题目和完全背包问题很类似。 这题目和完全背包问题很类似。基本的方程只需将完全背包 目和完全背包问题很类似 问题的方程略微一改即可, 问题的方程略微一改即可,因为对于第 i 种物品有 n[i]+1

种策略: ……取 n[i]件 f[i][v]表示前 种策略:取 0 件,取 1 件……取 n[i]件。令 f[i][v]表示前 的背包的最大权值, i 种物品恰放入一个容量为 v 的背包的最大权值 , 则 : f[i][v]=max{f[i-1][vk*w[i]|0<=k<=n[i]}。 f[i][v]=max{f[i-1][v-k*c[i]]+ k*w[i]|0<=k<=n[i]}。复 O(V*∑n[i])。 杂度是 O(V*∑n[i])。

转化为 01 背包问题 背包求解: 另一种好想好写的基本方法是转化为 01 背包求解:把第 i n[i]件 背包中的物品,则得到了物品数为∑ 种物品换成 n[i]件 01 背包中的物品,则得到了物品数为∑ n[i]的 背包问题, 直接求解, O(V*∑n[i])。 n[i]的 01 背包问题, 直接求解, 复杂度仍然是 O(V*∑n[i])。

但是我们期望将它转化为 01 背包问题之后能够像完全背包 一样降低复杂度。仍然考虑二进制的思想, 一样降低复杂度。仍然考虑二进制的思想,我们考虑把第 i 种物品换成若干件物品, 种物品换成若干件物品,使得原问题中第 i 种物品可取的每 种策略——取 0..n[i]件——均能等价于取若干件代换以后 种策略——取 0..n[i]件——均能等价于取若干件代换以后 —— 的物品。另外, n[i]件的策略必不能出现 件的策略必不能出现。 的物品。另外,取超过 n[i]件的策略必不能出现。

方法是: 种物品分成若干件物品, 方法是:将第 i 种物品分成若干件物品,其中每件物品有一 个系数, 个系数,这件物品的费用和价值均是原来的费用和价值乘以 这 个 系 数 。 使 这 些 系 数 分 别 为

1,2,4,...,2^(k-1),n[i]-2^k+1, 且 [i]1,2,4,...,2^(k-1),n[i]-2^k+1, k 是满足 n[i]-2^k+1>0 的最大整数。例如, n[i]为 13, 的最大整数。例如,如果 n[i]为 13,就将这种物品分成系 的四件物品。 数分别为 1,2,4,6 的四件物品。

n[i], 分成的这几件物品的系数和为 n[i], 表明不可能取多于 n[i] 种物品。 0..n[i]间的 件的第 i 种物品。另外这种方法也能保证对于 0..n[i]间的 每一个整数,均可以用若干个系数的和表示, 每一个整数,均可以用若干个系数的和表示,这个证明可以 0..2^k2^k..n[i]两段来分别讨论得出 并不难, 两段来分别讨论得出, 并不难, 分 0..2^k-1 和 2^k..n[i]两段来分别讨论得出, 希 望你自己思考尝试一下。 望你自己思考尝试一下。

n[i])种物品 种物品, 这样就将第 i 种物品分成了 O(log n[i])种物品,将原问题 O(V*∑ n[i])的 背包问题, 转化为了复杂度为 O(V*∑log n[i])的 01 背包问题,是很大 的改进。 的改进。

O(VN)的算法 O(VN)的算法 O(VN)的算法 的算法。 多重背包问题同样有 O(VN)的算法。这个算法基于基本算法 的状态转移方程, 的状态转移方程,但应用单调队列的方法使每个状态的值可 O(1)的时间求解 的时间求解。 以以均摊 O(1)的时间求解。由于用单调队列优化的 DP 已超 的范围,故本文不再展开讲解。 出了 NOIP 的范围,故本文不再展开讲解。我最初了解到这 个方法是在楼天成的“男人八题”幻灯片上。 个方法是在楼天成的“男人八题”幻灯片上。

小结 O(V*∑n[i])改进到 这里我们看到了将一个算法的复杂度由 O(V*∑n[i])改进到 O(V*∑ n[i])的过程 的过程, O(V*∑log n[i])的过程,还知道了存在应用超出 NOIP 范围 O(VN)算法 希望你特别注意“拆分物品” 算法。 的知识的 O(VN)算法。希望你特别注意“拆分物品”的思想

和方法,自己证明一下它的正确性, 和方法,自己证明一下它的正确性,并用尽量简洁的程序来 的正确性 实现。 实现。

P04: 混合三种背包问题 问题 P01、P02、 混合起来。也就是说, 如果将 P01、P02、P03 混合起来。也就是说,有的物品只可 以取一次( 背包) 有的物品可以取无限次(完全背包) ,有的物品可以取无限次 以取一次(01 背包) 有的物品可以取无限次(完全背包) , , 有的物品可以取的次数有一个上限(多重背包) 。应该怎么 有的物品可以取的次数有一个上限(多重背包) 应该怎么 。 求解呢? 求解呢?

01 背包与完全背包的混合 中最后给出的伪代码只有一处不同, 考虑到在 P01 和 P02 中最后给出的伪代码只有一处不同,故 如果只有两类物品:一类物品只能取一次, 如果只有两类物品:一类物品只能取一次,另一类物品可以 取无限次,那么只需在对每个物品应用转移方程时, 取无限次,那么只需在对每个物品应用转移方程时,根据物 品的类别选用顺序或逆序的循环即可, O(VN)。 品的类别选用顺序或逆序的循环即可,复杂度是 O(VN)。伪 代码如下: 码如下:

for i=1..N if 第 i 件物品是 01 背包 for v=V..0

f[v]=max{f[v],f[vf[v]=max{f[v],f[v-c[i]]+w[i]}; else if 第 i 件物品是完全背包 for v=0..V f[v]=max{f[v],f[vf[v]=max{f[v],f[v-c[i]]+w[i]};

再加上多重背包 如果再加上有的物品最多可以取有限次, 如果再加上有的物品最多可以取有限次,那么原则上也可以 O(VN)的解法 的解法: 给出 O(VN)的解法:遇到多重背包类型的物品用单调队列解 即可。 范围的算法的话, 即可。但如果不考虑超过 NOIP 范围的算法的话,用 P03 中 n[i])个 将每个这类物品分成 O(log n[i])个 01 背包的物品的方法也 已经很优了。 已经很优了。

小结 有人说,困难的题目都是由简单的题目叠加而来的。 有人说,困难的题目都是由简单的题目叠加而来的。这句话 是否公理暂且存之不论, 是否公理暂且存之不论,但它在本讲中已经得到了充分的体 背包、完全背包、多重背包都不是什么难题, 现。本来 01 背包、完全背包、多重背包都不是什么难题, 但将它们简单地组合起来以后就得到了这样一道一定能吓 倒不少人的题目。但只要基础扎实, 倒不少人的题目。但只要基础扎实,领会三种基本背包问题 的思想, 的思想 , 就可以做到把困难的题目拆分成简单的题目来解 决。 P05: 二维费用的背包问题 问题

二维费用的背包问题是指:对于每件物品, 二维费用的背包问题是指:对于每件物品,具有两种不同的 费用;选择这件物品必须同时付出这两种代价; 费用;选择这件物品必须同时付出这两种代价;对于每种代 价都有一个可付出的最大值(背包容量) 。问怎样选择物品 价都有一个可付出的最大值(背包容量) 问怎样选择物品 一个可付出的最大值 。 可以得到最大的价值。 设这两种代价分别为代价 1 和代价 2, 可以得到最大的价值。 a[i]和 b[i]。 第 i 件物品所需的两种代价分别为 a[i]和 b[i]。两种代价 可付出的最大值(两种背包容量) 可付出的最大值(两种背包容量)分别为 V 和 U。物品的价 w[i]。 值为 w[i]。

算法 费用加了一维, 只需状态也加一维即可。 f[i][v][u]表示 设 费用加了一维, 只需状态也加一维即可。 f[i][v][u]表示 时可获得的最大价值。 前 i 件物品付出两种代价分别为 v 和 u 时可获得的最大价值。 状 态 转 移 方 程 就 是 : f

[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w [i]}。如前述方法,可以只使用二维的数组: [i]}。如前述方法,可以只使用二维的数组:当每件物品只 维的数组 采用顺序的循环, 可以取一次时变量 v 和 u 采用顺序的循环,当物品有如完全 背包问题时采用逆序的循环。 背包问题时采用逆序的循环。当物品有如多重背包问题时拆 分物品。 分物品。

物品总个数的限制 有时, 二维费用”的条件是以这样一种隐含的方式给出的: “ 有时, 二维费用”的条件是以这样一种隐含的方式给出的: 件物品。 最多只能取 M 件物品。 这事实上相当于每件物品多了一种 件 “ 数”的费用,每个物品的件数费用均为 1,可以付出的最大 的费用,

换句话说, f[v][m]表示付出费用 件数费用为 M。换句话说,设 f[v][m]表示付出费用 v、最多 件时可得到的最大价值, 完全、 选 m 件时可得到的最大价值, 则根据物品的类型 01、 (01、 完全、 多重)用不同的方法循环更新, f[0..V][0..M]范围 多重)用不同的方法循环更新,最后在 f[0..V][0..M]范围 内寻找答案。 内寻找答案。

另外,如果要求“ 件物品” f[0..V][M]范围内 另外,如果要求“恰取 M 件物品” 则在 f[0..V][M]范围内 , 寻找答案。 寻找答案。

小结 事实上,当发现由熟悉的动态规划题目变形得来的题目时, 事实上,当发现由熟悉的动态规划题目变形得来的题目时, 在原来的状态中加一纬以满足新的限制是一种比较通用的 方法。希望你能从本讲中初步体会到这种方法。 方法。希望你能从本讲中初步体会到这种方法。

P06: 分组的背包问题 问题 的背包。 有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i], w[i]。这些物品被划分为若干组, c[i],价值是 w[i]。这些物品被划分为若干组,每组中的物 品互相冲突,最多选一件。 品互相冲突,最多选一件。求解将哪些物品装入背包可使这 些物品的费用总和不超过背包容量,且价值总和最大。 些物品的费用总和不超过背包容量,且价值总和最大。

算法 这个问题变成了每组物品有若干种策略: 这个问题变成了每组物品有若干种策略:是选择本组的某一

f[k][v]表示前 件,还是一件都不选。也就是说设 f[k][v]表示前 k 组物品 还是一件都不选。 花 费 费 用 v 能 取 得 的 最 大 权 值 , 则 有

f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品 f[k][v]=max{f[k-1][v],f[k-1][v-c[i]]+w[i]|物品 i 属于 第 k 组 }。

使用一维数组的伪代码如下: 使用一维数组的伪代码如下:

for 所有的组 k for 所有的 i 属于组 k for v=V..0 f[v]=max{f[v],f[vf[v]=max{f[v],f[v-c[i]]+w[i]}

另外, 另外,显然可以对每组中的物品应用 P02 中“一个简单有效 的优化” 。 的优化”

小结 分组的背包问题将彼此互斥的若干物品称为一个组, 分组的背包问题将彼此互斥的若干物品称为一个组,这建立 题将彼此互斥的若干物品称为一个组 了一个很好的模型。 了一个很好的模型。不少背包问题的变形都可以转化为分组 ( P07) 的背包问题 例如 P07) 由分组的背包问题进一步可定义 泛 , “ 化物品”的概念,十分有利于解题。 化物品”的概念,十分有利于解题。

P07: 有依赖的背包问题

简化的问题 “依赖” 的关系。 也就是说, 这种背包问题的物品间存在某种 依赖” 的关系。 也就是说, i 依赖于 j,表示若选物品 i,则必须选物品 j。为了简化起 见,我们先设没有某个物品既依赖于别的物品,又被别的物 我们先设没有某个物品既依赖于别的物品, 品所依赖;另外,没有某件物品同时依赖多件物品。 品所依赖;另外,没有某件物品同时依赖多件物品。

算法 金明的预算方案一题扩展而来。 这个问题由 NOIP2006 金明的预算方案一题扩展而来。遵从 题的提法,将不依赖于别的物品的物品称为“主件” 该题的提法,将不依赖于别的物品的物品称为“主件” 依 , 赖于某主件的物品称为“附件” 赖于某主件的物品称为“附件” 由这个问题的简化条件可 。 知所有的物品由若干主件和依赖于每个主件的一个附件集 合组成。 合组成。

按照背包问题的一般思路, 按照背包问题的一般思路 , 仅考虑一个主件和它的附件集 合。可是,可用的策略非常多,包括:一个也不选,仅选择 可是,可用的策略非常多,包括:一个也不选, 主件,选择主件后再选择一个附件, 主件,选择主件后再选择一个附件,选择主件后再选择两个 附件……无法用状态转移方程来表示如此多的策略 ( (事实 附件……无法用状态转移方程来表示如此多的策略。 事实 ……无法用状态转移方程来表示如此多的策略。 个附件, 为指数级。 上,设有 n 个附件,则策略有 2^n+1 个,为指数级。 )

考虑到所有这些策略都是互斥的(也就是说, 考虑到所有这些策略都是互斥的(也就是说,你只能选择一 种策略) 所以一个主件和它的附件集合实际上对应于 ,所以一个主件和它的附 种策略) 所以一个主件和它的附件集合实际上对应于 P06 , 中的一个物品组, 中的一个物品组,每个选择了主件又选择了若干个附件的策

略对应于这个物品组中的一个物品, 略对应于这个物品组中的一个物品,其费用和价值都是这个 策略中的物品的值的和。 策略中的物品的值的和。但仅仅是这一步转化并不能给出一 个好的算法, 个好的算法,因为物品组中的物品还是像原问题的策略一样 多。

中的一句话: 再考虑 P06 中的一句话: 可以对每组中的物品应用 P02 中 一个简单有效的优化” 这提示我们, “一个简单有效的优化” 这提示我们,对于一个物品组中 。 的物品,所有费用相同的物品只留一个价值最大的, 的物品,所有费用相同的物品只留一个价值最大的,不影响 结果。所以, 附件集合” 结果。所以,我们可以对主件 i 的“附件集合”先进行一次 背包, 0..V-c[i]所有这些值时相应 所有这些值时相应的最 01 背包,得到费用依次为 0..V-c[i]所有这些值时相应的最 f'[0..V-c[i]]。 大价值 f'[0..V-c[i]]。那么这个主件及它的附件集合相当 个物品的物品组, 于 V-c[i]+1 个物品的物品组,其中费用为 c[i]+k 的物品的 f'[k]+w[i]。 价值为 f'[k]+w[i]。 也就是说原来指数级的策略中有很多策 略都是冗余的, 背包后, 略都是冗余的 , 通过一次 01 背包后 , 将主件 i 转化为 个物品的物品组, V-c[i]+1 个物品的物品组, 就可以直接应用 P06 的算法解决 问题了。 问题了。

更一般的问题 更一般的问题是: 依赖关系以图论中 森林” “森林” 的形式给出 森 ( 更一般的问题是: 林即多叉树的集合) 也就是说, ,也就是说 林即多叉树的集合) 也就是说,主件的附件仍然可以具有 , 自己的附件集合, 自己的附件集合,限制只是每个物品最多只依赖于一个物品 (只有一个主件)且不出现循环依赖。 只有一个主件) 不出现循环依赖。

解决这个问题仍然可以用将每个主件及其附件集合转化为 物品组的方式。唯一不同的是,由于附件可能还有附件, 物品组的方式。唯一不同的是,由于附件可能还有附件,就 背包中的物品了。 不能将每个附件都看作一个一般的 01 背包中的物品了。若 这个附件也有附件集合,则它必定要被先转化为物品组, 这个附件也有附件集合,则它必定要被先转化为物品组,然 后用分组的背包问题解出主件及其附件集合所对应的附件 组中各个费用的附件所对应的价值。 组中各个费用的附件所对应的价值。

事实上, DP, 事实上,这是一种树形 DP,其特点是每个父节点都需要对它 以求得自己的相关属性。 的各个儿子的属性进行一次 DP 以求得自己的相关属性。这 已经触及到了“泛化物品”的思想。 已经触及到了“泛化物品”的思想。看完 P08 后,你会发现 这个“依赖关系树”每一个子树都等价于一件泛化物品, 这个“依赖关系树”每一个子树都等价于一件泛化物品,求 于一件泛化物品 某节点为根的子树对应的泛化物品相当于求其所有儿子的 对应的泛化物品之和。 对应的泛化物品之和。

小结 的那道背包问题我做得很失败, NOIP2006 的那道背包问题我做得很失败,写了上百行的代 码,却一分未得。后来我通过思考发现通过引入“物品组” 却一分未得。后来我通过思考发现通过引入“物品组” 和“依赖”的概念可以加深对这题的理解,还可以解决它的 依赖”的概念可以加深对这题的理解, 推广问题。 推广问题 。 用物品组的思想考虑那题中极其特殊的依赖关 物品不能既作主件又作附件, 每个主件最多有两个附件, 系: 物品不能既作主件又作附件, 每个主件最多有两个附件, 可以发现一个主件和它的两个附件等价于一个由四个物品

组成的物品组,这便揭示了问题的某种本质。 组成的物品组,这便揭示了问题的某种本质。

我想说: 失败不是什么丢人的事情, 从失败中全无收获才是。 我想说: 失败不是什么丢人的事情, 从失败中全无收获才是。 才是

P08: 泛化物品 定义 考虑这样一种物品,它并没有固定的费用和价值, 考虑这样一种物品,它并没有固定的费用和价值,而是它的 价值随着你分配给它的费用而变化。 价值随着你分配给它的费用而变化 。 这就是泛化物品的概 念。

更严格的定义之。 的背包问题中, 更严格的定义之。在背包容量为 V 的背包问题中,泛化物品 是一个定义域为 0..V 中的整数的函数 h, 当分配给它的费用 h(v)。 为 v 时,能得到的价值就是 h(v)。

这个定义有一点点抽象, 这个定义有一点点抽象,另一种理解是一个泛化物品就是一 h[0..V], h[V]。 个数组 h[0..V],给它费用 v,可得到价值 h[V]。

的物品, 背包中的物品, 一个费用为 c 价值为 w 的物品,如果它是 01 背包中的物品, 那么把它看成泛化物品, 那么把它看成泛化物品,它就是除了 h(c)=w 其它函数值都 的一个函数。如果它是完全背包中的物品, 为 0 的一个函数。如果它是完全背包中的物品,那么它可以 看成这样一个函数, 仅当 v 被 c 整除时有 h(v)=v/c*w, h(v)=v/c*w, 看成这样一个函数, 其它 函数值均为 0。如果它是多重背包中重复次数最多为 n 的物

那么它对应的泛化物品的函数有 h(v)=v/c*w 仅当 v 被 c 品, v/c<=n, 整除且 v/c<=n,其它情况函数值均为 0。

一个物品组可以看作一个泛化物品 h。 对于一个 0..V 中的 v, 的的物品, h(v)=0, 若物品组中不存在费用为 v 的的物品, h(v)=0, 则 否则 h(v) 的物品的最大价值。 为所有费用为 v 的物品的最大价值。P07 中每个主件及其附 件集合等价于一个物品组,自然也可看作一个泛化物品。 件集合等价于一个物品组,自然也可看作一个泛化物品。

泛化物品的和 如果面对两个泛化物品 h 和 l,要用给定的费用从这两个泛 化物品中得到最大的价值,怎么求呢?事实上, 化物品中得到最大的价值,怎么求呢?事实上,对于一个给 定的费用 v,只需枚举将这个费用如何分配给两个泛化物品 就可以了。同样的, 就可以了。同样的,对于 0..V 的每一个整数 v,可以求得费 f(v)。 用 v 分配到 h 和 l 中的最大价值 f(v)。也即 f(v)=max{h(k) +l(v-k)|0<=k<=v}。可以看到, +l(v-k)|0<=k<=v}。可以看到,f 也是一个由泛化物品 h 和 的函数,也就是说, l 决定的定义域为 0..V 的函数,也就是说,f 是一个由泛化 决定的泛化物品。 物品 h 和 l 决定的泛化物品。

由此可以定义泛化物品的和: 都是泛化物品,若泛化物 由此可以定义泛化物品的和:h、l 都是泛化物品,若泛化物 f(v)=max{h(k)+l(v-k)|0<=k<=v}, 品 f 满足 f(v)=max{h(k)+l(v-k)|0<=k<=v},则称 f 是 h 与 的和, f=h+l。 O(V^2)。 l 的和,即 f=h+l。这个运算的时间复杂度是 O(V^2)。

泛化物品的定义表明:在一个背包问题中, 泛化物品的定义表明:在一个背包问题中,若将两个泛化物 品代以它们的和,不影响问题的答案。事实上, 品代以它们的和,不影响问题的答案。事实上,对于其中的 物品都是泛化物品的背包问题, 物品都是泛化物品的背包问题,求它的答案的过程也就是求 所有这些泛化物品之和的过程。 所有这些泛化物品之和的过程 。 设此和为 s , 则答案就是 s[0..V]中的最大值。 s[0..V]中的最大值。 中的最大值

背包问题的泛化物品 一个背包问题中,可能会给出很多条件, 一个背包问题中,可能会给出很多条件,包括每种物品的费 用、价值等属性,物品之间的分组、依赖等关系等。但肯定 价值等属性,物品之间的分组、依赖等关系等。 能将问题对应于某个泛化物品。也就是说, 能将问题对应于某个泛化物品。也就是说,给定了所有条件 以后, 求得: 以后,就可以对每个非负整数 v 求得:若背包容量为 v,将 物品装入背包可得到的最大价值是多少, 物品装入背包可得到的最大价值是多少,这可以认为是定义 在非负整数集上的一件泛化物品。这个泛化物品——或者说 在非负整数集上的一件泛化物品。这个泛化物品——或者说 —— 问题所对应的一个定义域为非负整数的函数——包含了关 问题所对应的一个定义域为非负整数的函数 ——包含了关 —— 于问题本身的高度浓缩的信息。一般而言, 于问题本身的高度浓缩的信息。一般而言,求得这个泛化物 品的一个子域( 0..V)的值之后, 品的一个子域(例如 0..V)的值之后,就可以根据这个函数 的取值得到背包问题的最终答案。 的取值得到背包问题的最终答案。

综上所述,一般而言,求解背包问题, 综上所述,一般而言,求解背包问题,即求解这个问题所对 应的一个函数,即该问题的泛化物品。 应的一个函数,即该问题的泛化物品。而求解某个泛化物品 的一种方法就是将它表示为若干泛化物品的和然后求之。 的一种方法就是将它表示为若干泛化物品的和然后求之。 方法就是将它表示为若干泛化物品的和然后求之

小结 本讲可以说都是我自己的原创思想。具体来说, 本讲可以说都是我自己的原创思想。具体来说,是我在学习 语言时, 函数式编程的 Scheme 语言时,用函数编程的眼光审视各类 背包问题得出的理论。这一讲真的很抽象,也许在“ 背包问题得出的理论。这一讲真的很抽象,也许在“模型的 抽象程度” 的要求, 抽象程度”这一方面已经超出了 NOIP 的要求,所以暂且看 不懂也没关系。 之路逐渐延伸, 不懂也没关系。相信随着你的 OI 之路逐渐延伸,有一天你 会理解的。 会理解的。

我想说: 思考” “ 最重要的品质。简单的问题, 我想说: 思考”是一个 OIer 最重要的品质。简单的问题, 深入思考以后,也能发现更多。 深入思考以后,也能发现更多。

P09: 背包问题问法的变化 以上涉及的各种背包问题都是要求在背包容量(费用) 以上涉及的各种背包问题都是要求在背包容量(费用)的限 制下求可以取到的最大价值, 制下求可以取到的最大价值,但背包问题还有很多种灵活的 问法,在这里值得提一下。但是我认为, 问法,在这里值得提一下。但是我认为,只要深入理解了求 背包问题最大价值的方法,即使问法变化了, 背包问题最大价值的方法,即使问法变化了,也是不难想出 算法的。 算法的。

例如, 例如,求解最多可以放多少件物品或者最多可以装满多少背 包的空间。 包的空间。这都可以根据具体问题利用前面的方程求出所有 状态的值( 数组)之后得到。 状态的值(f 数组)之后得到。

还有,如果要求的是“总价值最小” 总件数最小” “总件数最小 , 还有,如果要求的是“总价值最小” 总件数最小” 只需简 “ 即可。 单的将上面的状态转移方程中的 max 改成 min 即可。

下面说一些变化更大的问法。 下面说一些变化更大的问法。

输出方案 一般而言,背包问题是要求一个最优值,如果要求输出这个 一般而言,背包问题是要求一个最优值,如果要求输出这个 最优值的方案, 最优值的方案 , 可以参照一般动态规划问题输出方案的方 法:记录下每个状态的最优值是由状态转移方程的哪一项推 出来的,换句话说,记录下它是由哪一个策略推出来的。 出来的,换句话说,记录下它是由哪一个策略推出来的。便 可根据这条策略找到上一个状态, 可根据这条策略找到上一个状态,从上一个状态接着向前推 即可。 即可。







01

















f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 再用一个 f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。 [v], f[i][v]的值时是采 数组 g[i] [v],设 g[i][v]=0 表示推出 f[i][v]的值时是采 用了方程的前一项( f[i][v]=f[i-1][v]) g[i][v]表 ,g[i][v] 用了方程的前一项(也即 f[i][v]=f[i-1][v]) g[i][v]表 , 示采用了方程的后一项。注意这两项分别表示了两种策略: 示采用了方程的后一项。注意这两项分别表示了两种策略: 一项 个物品。 未选第 i 个物品及选了第 i 个物品。那么输出方案的伪代码 可以这样写( f[N][V]) 可以这样写(设最终状态为 f[N][V]) :

i=N

v=V while(i>0) if(g[i][v]==0) "未选第 项物品" print "未选第 i 项物品" else if(g[i][v]==1) "选了第 项物品" print "选了第 i 项物品" v=vv=v-c[i]

另外, 另外,采用方程的前一项或后一项也可以在输出方案的过程 f[i][v]的值实时地求出来 的值实时地求出来, 数组, 中根据 f[i][v]的值实时地求出来,也即不须纪录 g 数组, f[i][v]==f[i 1][v], f[i将上述代码中的 g[i] [v]==0 改成 f[i][v]==f[i-1][v], f[i][v]==f[i-1][v-c[i]]+w[i]也可 也可。 g[i][v]==1 改成 f[i][v]==f[i-1][v-c[i]]+w[i]也可。

输出字典序最小的最优方案 这里“字典序最小” 这里“字典序最小”的意思是 1..N 号物品的选择方案排列 出来以后字典序最小。 出来以后字典序最小。以输出 01 背包最小字典序的方案为 例。

一般而言,求一个字典序最小的最优方案, 一般而言,求一个字典序最小的最优方案,只需要在转移时 注意策略。首先,子问题的定义要略改一些。我们注意到, 注意策略。首先,子问题的定义要略改一些。我们注意到, 的最优方案, 如果存在一个选了物品 1 的最优方案,那么答案一定包含物 c[1], 品 1,原问题转化为一个背包容量为 v-c[1],物品为 2..N

的子问题。反之, 的子问题。反之,如果答案不包含物品 1,则转化成背包容 的子问题。不管答案怎样, 量仍为 V,物品为 2..N 的子问题。不管答案怎样,子问题的 的形式来定义的, 物品都是以 i..N 而非前所述的 1..i 的形式来定义的,所以 状态的定义和转移方程都需要改一下。 状态的定义和转移方程都需要改一下。但也许更简易的方法 是先把物品逆序排列一下, 是先把物品逆序排列一下 , 以下按物品已被逆序排列来叙 述。

在这种情况下,可以按照前面经典的状态转移方程来求值, 在这种情况下,可以按照前面经典的状态转移方程来求值, 只是输出方案的时候要注意 : 从 N 到 1 输入时 , 如果 f[i][v]==f[i-v]及 f[i][v]==f[i-1][f-c[i]]+w[i]同时成 f[i][v]==f[i-v]及 f[i][v]==f[i-1][f-c[i]]+w[i]同时成 来输出方案。 立,应该按照后者(即选择了物品 i)来输出方案。 应该按照后者(

求方案总数 对于一个给定了背包容量、物品费用、物品间相互关系( 对于一个给定了背包容量、物品费用、物品间相互关系(分 包容量 组、依赖等)的背包问题,除了再给定每个物品的价值后求 依赖等)的背包问题, 可得到的最大价值外, 可得到的最大价值外,还可以得到装满背包或将背包装至某 一指定容量的方案总数。 一指定容量的方案总数。

对于这类改变问法的问题, 对于这类改变问法的问题 , 一般只需将状态转移方程中的 即可。 背包中的物品, max 改成 sum 即可。例如若每件物品均是 01 背包中的物品, 转 移 方 程 即 为

f[i][v]=sum{f[i-1][v],f[i-1][v-c[i]]+w[i]}, 初始条件 f[i][v]=sum{f[i-1][v],f[i-1][v-c[i]]+w[i]},

f[0][0]=1。 f[0][0]=1。

事实上, 事实上,这样做可行的原因在于状态转移方程已经考察了所 有可能的背包组成方案。 有可能的背包组成方案。

最优方案的总数 这里的最优方案是指物品总价值最大的方案。 这里的最优方案是指物品总价值最大的方案。还是以 01 背 最优方案是指物品总价值最大的方案 包为例。 包为例。

结合求最大总价值和方案总数两个问题的思路, 结合求最大总价值和方案总数两个问题的思路,最优方案的 总数可以这样求:f[i][v]意义同前述,g[i][v]表示这个子 总数可以这样求:f[i][v]意义同前述,g[i][v]表示这个子 意义同前述 问题的最优方案的总数, f[i][v]的同时求 问题的最优方案的总数,则在求 f[i][v]的同时求 g[i][v] 的伪代码如下: 的伪代码如下:

for i=1..N for v=0..V f[i][v]=max{f[i-1][v],f[i-1][vf[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} g[i][v]=0 if(f[i][v]==f[iif(f[i][v]==f[i-1][v]) inc(g[i][v],g[iinc(g[i][v],g[i-1][v] if(f[i][v]==f[i-1][vif(f[i][v]==f[i-1][v-c[i]]+w[i]) inc(g[i][v],g[i-1][vinc(g[i][v],g[i-1][v-c[i]])

如果你是第一次看到这样的问题, 如果你是第一次看到这样的问题 , 请仔细体会上面的伪代 码。

小结 显然,这里不可能穷尽背包类动态规划问题所有的问法。 显然,这里不可能穷尽背包类动态规划问题所有的问法。甚 至还存在一类将背包类动态规划问题与其它领域( 至还存在一类将背包类动态规划问题与其它领域 ( 例如数 论、图论)结合起来的问题,在这篇论背包问题的专文中也 图论)结合起来的问题, 不会论及。 不会论及。但只要深刻领会前述所有类别的背包问题的思路 和状态转移方程,遇到其它的变形问法, 和状态转移方程,遇到其它的变形问法,只要题目难度还属 NOIP,应该也不难想出算法。 于 NOIP,应该也不难想出算法。

触类旁通、举一反三, 应有的品质吧。 触类旁通、举一反三,应该也是一个 OIer 应有的品质吧。 参考资料: 参考资料:来自 OIBH


背包问题九讲和源程序(答案)

背包问题九讲和源程序(答案)_计算机软件及应用_IT/计算机_专业资料。背包问题九讲和源程序(答案).txt 台湾一日不收复,我一日不过 4 级!如果太阳不出来了,我...

背包9讲

动态规划中背包问题动态规划中背包问题隐藏>> 背包九讲(转载) 背包九讲(转载)第一讲 01 背包问题 这是最基本的背包问题, 每个物品最多只能放一 次。 第二讲...

背包问题九讲和源程序(答案)

背包问题九讲和源程序(答案).txt 台湾一日不收复,我一日不过 4 级!如果太阳不出来了, 我就不去上班了;如果出来了,我就继续睡觉!目录 第一讲 01 背包问题 ...

7背包问题九讲之有依赖的背包问题

背包问题九讲 2.0 16页 免费 背包问题九讲 22页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

9背包问题九讲之背包问题文法的变化

9背包问题九讲背包问题文法的变化_电脑基础知识_IT/计算机_专业资料。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。P...

4背包问题九讲之混合三种背包问题

4背包问题九讲之混合三种背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。P04: 混合三种背包问题问题如果将 ...

5背包问题九讲之二维费用的背包问题

5背包问题九讲之二维费用的背包问题_电脑基础知识_IT/计算机_专业资料。选填,简要介绍文档的主要内容,方便文档被更多人浏览和下载。P...