组合问题

总述

• 寻找（明确地、隐含地）寻找一个组合对象

  • 排列
  • 组合（整数规划）
  • 子集

• 这些对象能满足特定条件并具有想要的属性

  • 价值最大化
  • 成本最小化

特点

无论从理论角度、实践角度而言，组合问题是计算领域最难的问题

• 随着问题规模增大，组合对象数量增长极快

• 没有一种已知算法，能在可接受的时间范围内，精确的解决 大部分组合问题，且被普遍认为不存在（未被证实）

• 有些组合问题有高效求解算法，是幸运的例外

从更抽象的角度看，旅行商问题、图填色问题也是组合问题的特例

思路

• exhaustive search：（穷举搜索）是简单的蛮力方法

  • 生成问题域每个元素
  • 选出满足问题约束的元素
  • 最后寻找期望元素

• 因为可能性太多，基本可能从动态规划方向着手

背包问题

给定n个重量为$w_1, w_2, \cdots, w_n$价值为$v_1, v_2, …, vn$ 的物品和承重为$W$的背包，求能够装进背包的最有价值物品子集

蛮力算法

算法

• 考虑所有n个物品的子集
• 计算每个子集重量，找出可行子集
• 找到可行子集中价值最大子集

经典自底向上动态规划

依次求解所有子问题、记录

算法

设$F(i, j)$为由前i个物品、承重量为j的背包得到最优解

• 不包括第i个物品的子集中，最优子集价值为$F(i-1, j)$

• 包括第i个物品的子集中，最优子集是由该物品和前i-1个物品 中能够放进承重量为$j-w_i$的背包的最优子集组成，总价值为 $v_i + F(i-1, j-w_i)$

则递推式为

$$F(i, j) = \left \{ \begin{array}{l} max\{F(i-1, j), v_i + F(i-1, j-w_i)\} & j-w_i \geqslant 0 \\ F(i-1, j) & j-w_i \leqslant 0 \\ 0 & i=0 or j=0 (i, j \geqslant 0) \end{array} \right.$$

Knapsack(Ws[1..n], Vs[1..n], W)
	// 动态规划求解背包问题
	// 输入：Ws[1..n]物品重量、Vs[1..n]物品价值，W背包承重
	// 输出：背包能够装载的最大价值
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
		for i = 1 to n do
			if j >= Ws[i]:
				F[i, j] = max(F[i-1, j], Vs[i] + F[i-1, j-Ws[i])
				// 这里用于比较的F值，在之前的循环中已经确定
			else
				F[i, j] = F[i-1, j]
	return F[n, W]

算法特点

• 算法效率
  • 时间效率$\in \Theta(nW)$
  • 空间效率$\in \Theta(nW)$
  • 回溯求最优解组成效率$\in O(n)$

自顶向下动态规划

算法

MFKnapsack(i, j)
	// 背包问题的记忆功能方法
	// 输入：i考虑的物品数量，j背包承重
	// 输出：前i个物品的最优可行子集
	// Ws[1..n]、Vs[1..n]、F[0..n, 0..W]作为全局变量
	for i = 0 to n do
		F[i, 0] = 0
	for j = 0 to W do
		F[0, j] = 0
	if F[i, j] < 0
		if j < Ws[i]
			value = MFKnapsack(i-1, j)
		else
			value = max(MFKnapsack(i-1, j),
				Vs[i] + MFKnapsack(i-1, j - Ws[i]))
		F[i, j] = value
	return F[i, j]

算法特点

• 算法效率
  • 相较于经典自底向上算法，时间效率提升常数因子，但是 效率仍然$\in \Theta(nW)$
  • 相较于自底向上算法空间优化版版本而言，空间效率较低

分支界限法

• 不失一般性认为，物品按照价值重量比$v_i / w_i$降序排列， 可以简化问题

• 第i层节点上界可取$ub = v + (W - w)(v{i+1} / w{i+1})$

  • $v$：已选物品价值
  • $W - w$：背包剩余承重量
  • $v{i+1}/w{i+1}$：剩余物品单位单位最大价值

• 更紧密、复杂的上界 $ub = v + \sum{k=i+1}^K v_k + (W - \sum{k=1}^K w_k)v_K / w_K$

算法

特点

• 分支界限法求解背包问题中，每个中间节点都是给定物品的子集 ，是背包问题的可行解

背包问题近似算法

贪婪算法

算法

• 对物品按照价值重量比$r_i = v_i / w_i, i=1,2,\cdots,n$ 降序排列

• 重复以下直到有序列表中不留下物品

  • 如果列表中当前物品可以装入，则放入背包并处理下个物品
  • 否则忽略，直接处理下个物品

特点

• 原始的贪婪算法解的精确率没有上界

  • 考虑：承重量为$W$背包，如下物品

    |物品|重量|价值|价值/重量| |——-|——-|——-|——-| |1|1|2|2| |2|w|w|1|

  • 则近似解精确率$r(s_a) = W/2$无上界

• 增强版贪婪算法：取贪婪算法解、能装载的价值最大单个物品 价值中较大者

  • 此改进的性能比可以降到2

近似方案

背包问题的存在多项式时间的系列算法，可以调节算法中参数$k$ 得到满足任意预定义精确率的近似解$s_a^{(k)}$

$$\frac {f(s^{*})} {f(s_a^{(k)}} \leqslant 1 + 1/k, k=1,2,\cdots, n-1$$

Sahni方案

• 生成所有小于k个物品的子集
• 向贪婪算法一样，向每个能装入背包的子集添加剩余物品中 价值重量比最大者
• 得到最有价值的修改后子集作为结果返回

Fully Polynomial Scheme

完全多项式方案

特点

• Sahni方案理论意义远大于实用价值

  • 其效率$\in O(kn^{k+1})$是n的多项式函数
  • 但是是k的指数函数

• 完全多项式方案更加复杂，但没有效率为参数k指数的缺陷

Bin-Packing Problem

装箱问题：给定n个问题，大小都是不超过1的有理数，将其装进数量 最少的大小为1的箱子中

Graph-Coloring Problem

图着色问题：对给定图，求使得任何两个相邻顶点颜色都不同时， 需要分配给图顶点的颜色数量

划分问题

给定n个正整数${a_i, i=1,2,\cdots}，判定能够将其划分为和相等 的两个子集

Subset-Sum Problem

给定n个正整数${a_i, i=1,2,\cdots}$，求子集$S$和为正整数d

回溯算法

约束

$$s + a_{i+1} > d \\ s + \sum_{j=i+1}^n a_j < d$$

• 其中$s$为考虑考虑第i+1元素时，前i个元素选情况下的和

算法

• 假设集合元素按升序排列

• 根节点为未选择任何元素

• 依次考虑将元素$a_i$添加进子集S中

  • 若满足约束条件、下个元素未考虑，继续考虑
  • 否则回溯，重新考虑父母节点

• 直到找到子集满足和为d，或第二次回溯到根节点

特点

币值最大化

给定一排n个硬币，币值为正整数$c_i, i=1, 2, \cdots, n$（币值 不唯一），在原始位置不相邻的情况下，使得所选硬币总金额最大

动态规划

算法

记最大可选金额为$F(n)$将可行规划分为两组

• 包含最后一枚硬币，最大金额为$c_n + F(n-2)$
• 不包含最后一枚硬币，最大金额为$F(n-1)$

则递推方程为

$$F(n) = max\{c_n + F(n-2), F(n-1)\}, n>1 \\ F(0) = 0, F(1) = c_1$$

CoinRow(C[1..n])
	// 在所选硬币不相邻，从一排硬币中选择最大金额
	// 输入：C[1..n]保存n个硬币面值
	// 输出：可选硬币最大金额
	F[0] = 1
	F[1] = C[1]
	for i = 2 to n do
		F[i] = max(C[i] + F[i-2], F[i-1])
	return F[n]

算法特点

• 时间效率$\in \Theta(n)$
• 空间效率$\in \Theta(n)$

找零问题

需找零金额为n，最少需要多少面值为$d_1 < d_2 < \cdots < d_n$ 的硬币，考虑$d_1 = 1$的一般情况

动态规划

算法

记$F(n)$为总金额为n的数量最少的硬币数目，定义$F(0)=0$

• 得到n的途径只能是在$n-d_j$上加入面值为$d_j$的硬币，其中 $j=1, 2, \cdots, m$，且$n \geqslant d_j$

• 考虑所有满足条件$d_j$，选择使得且$F(n - d_j)$最小者

则递推式有

$$F(n) = \left \{ \begin{array}{l} min \{ j: n \geqslant d_j \} \{ F(n - d_j) \} + 1 & n > 0 \\ 0 & n = 0 \end{array} \right.$$

ChangeMaking(D[1..m], n)
	// 动态规划法求解找零问题，d_1 = 1
	// 输入：正整数n，币值数组D[1..m]
	// 输出：总金额为n的最少硬币数目
	F[0] = 0
	for i = 1 to n do
		tmp = \infty
		j = 1
		while j <= m and i >= D[j] do
			tmp = min(F[i-D[j], tmp)
			j += 1
		F[i] = tmp + 1
	return F[n]

硬币收集问题

在n * m格木板中存放有硬币，每格硬币最多一个，寻找左上角(1,1) 到右下角(n, m)路径，使得能够收集尽可能多硬币，每次只能向下、 向右移动

动态规划

算法

记$F(i, j)$为截止到第i行、第j列单元格$(i, j)$能够收集到最大 硬币数

• 单元格$(i, j)$只能经由$(i-1, j)$、$(i, j-1)$达到
  • 初值1：假定$F(0, j)=0, F(i, 0)=0$
  • 初值2；递推求解$F[1, j], F[i, 1]$

则递推方程为

$$F(i, j) = \left \{ \begin{array}{l} max \{F(i-1 ,j), F(i, j-1)\} + c_{ij} & 1 <= i <= n, i <= j <= m \\ 0 & i = 0 or j = 0 \end{array} \right.$$

CoinCollection(C[1..n, 1..m])
	// 动态规划算法求解硬币收集问题
	// 输出：矩阵C[1..n, 1..m]表示单元格是否有硬币
	// 输出：在单元格[n, m]能够收集到的最大硬币数
	F[1, 1] = C[1, 1]
	for j = 2 to m do
		F[1, j] = F[1, j-1] + C[1, j]
		// 初始化首行
	for i = 2 to n do
		F[i, 1] = F[i-1, 1] + C[i, 1]
		for j = 2 to n do
			// 先填列
			F[i, j] = max(F[i-1, j], F[i, j-1]) + C[i, j]
	return F[n, m]

算法特点

• 算法效率
  • 计算每个单元格$F[i, j]$花费常量时间，所以算法时间 效率$\in \Theta(nm)$
  • 算法空间效率$\in Theta(nm)$

n皇后问题

将n个皇后放在$n * n$的棋盘上，使得皇后之间不能相互攻击

回溯算法

算法

算法特点

说明

• $n \geqslant 4$的n皇后问题都可以在线性时间内求解，已经 找到一些可选公式，用于计算n皇后的位置

生成排列

生成集合排列问题可以抽象为生成${1,\cdots,n}$所有$n!$个排列的 问题

• 假设$(n-1)!$个排列已经生成
• 则可以把n插入n-1个元素中可能的n个位置中去，得到较大规模 问题的解

最小变化

• 在元素上使用小箭头标记其方向： $\overleftarrow 1 \overleftarrow 2 \overleftarrow 3$
• 如果元素k的箭头指向相邻的较小元素，称在此排列中是移动的

减常量法

JohnsonTrotter(n)
	// 生成排列
	// 输入：正整数n
	// 输出：{1..n}所有排列列表
	将第一个排列初始化
	while 存在一个移动元素 do
		求最大的移动元素k
		把k和其箭头指向的相邻元素互换
		调转所有大于k的元素的方向
		将新排列添加到列表中

算法特点

• JsonTrotter是生成排列最有效算法之一，其运行时间和排列 数量成正比，即$\in \Theta(n!)$

字典序

减常量法

• 找到序列中最长递减后缀 $a{i+1} > a{i+2} > \cdots > a_{n}$
• 将$a_i$同序列中大于其的最小元素交换
• 将新后缀颠倒，使其变为递增序列，加入列表中

LexicographicPermute(n):
	// 以字典序产生排列
	// 输入：正整数n
	// 输出：字典序下，所有排列列表
	初始化第一个排列为12...n
	while 最后一个排列有两成连续升序元素 do
		找出使得a_i < a_{i+1}的最大的i
			// 即找到最长递减后缀
		找到使得a_i < a_j的最大索引
			// 即在后缀中大于其的最小元素索引
		交换a_i和a_j
		将a_{i+1}和a_{n}的元素反序
		将新排列添加至列表中

生成子集

集合$A[a_1, \cdots, a_n}$的所有子集可以分为两组

• 包含$a_n$：${a_1, \cdots, a_n}$的所有子集
• 不包含$a_n$的子集：把$a_n$添加进${a_1, \cdots, a_n}$子集 获得

• 同样的可以把集合抽象为位串，每个位串表示一个子集

减常量算法

字典序

按生成字典序（位串字典序）生成子集

• 将正序${1..n}$转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

挤压序

按照挤压序（位串挤压序）生成子集

• 将倒序{n..1}转换为二进制位串
• 依次按照二进制位串生成子集
  • 位串中为1表示对应元素在子集中

Squashed Order：所有包含$aj$子集必须紧排在所有包含 $a_1, \cdots, a{j-1}$的子集之后

最小变化

每个子集和其直接前趋之间，要么增加一个元素，要么减少一个元素

• 即每个位串和直接前趋之间仅仅相差一位

BRGC(n)
	// 递归生成二进制反射格雷码
	// 输入：正整数n
	// 输出：所有长度为n的格雷码位串列表
	if n == 1
		表L包含位串0、位串1
	else
		调用BRGC(n-1)生成长度为n-1的位串列表L1
		表L1倒序后复制给表L2
		把0加到表L1每个位串前
		表1加到表L2每个位串前
		把表L2添加到表L1后得到表L
	return L

球、桶问题

n个球放入m个桶中情况数量

球同、桶不同、无空桶

• 插板法

  $$\left \{ \begin{array}{l} C_{n-1}^{m-1}, & n \geq m \\ 0, & n < m \end{array} \right.$$

球同、桶不同、可空桶

• 插板法：可以假设m个桶中已经放好球，即m+n个相同球放入m个 不同桶、不允许空桶

  $$C_{n+m-1}^{m-1}$$

球同、桶同、可空桶

• 动态规划

  $$dp_4[i][j] = \left \{ \begin{array}{l} dp_4[i][j-1] + dp_4[i-j][j], & i \geq j \\ dp_4[i][j-1], & i < j \\ 1, & i=1,0 or j=1 \end{array} \right.$$

• 球数$i \geq j$桶数时递推式

  • 若有桶均包含球：剩余球可能性$dp[i-j][j]$
  • 若存在桶不包含球：剔除一个桶不影响总数
  • 没有其余情况

球同、桶同、无空桶

• 动态规划：由$dp_4$得到

  $$dp_5[i][j] = \left \{ \begin{array}{l} dp_4[i-j][j], & i \geq j \\ 0, & i < j \end{array} \right.$$

球不同、桶同、无空桶

• 第二类斯特林数

  $$dp[i][j] = \left \{ \begin{array}{l} j*dp[i-1][j] + dp[i-1][j-1], & 1 \leq j < i \\ 1, & i = j \\ 0, & i < j \end{array} \right.$$

• 球数$i>j$桶数时递推式

  • 考虑前$i-1$球已经占满所有桶，则最后球放入任何桶都是 新情况
  • 考虑前$i-1$只占满$j-1$个桶，则最后球必须放入空桶
  • 其他情况不可能

球不同、桶同、可空桶

• 在球不同、桶同、无空桶情况下枚举不空桶数目

  $$dp_2[i][j] = \sum_{k=1}^j dp[i][j]$$

球不同、桶不同、无空桶

• 在球不同、桶同、无空桶情况下对桶排序

  $$dp_3[i][j] = dp[i][j] * (j!)$$

球不同、桶不同、可空桶

• 每个球都有m中选择：$m^n$