组合问题

总述

  • 寻找(明确地、隐含地)寻找一个组合对象

    • 排列
    • 组合(整数规划)
    • 子集
  • 这些对象能满足特定条件并具有想要的属性

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

特点

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

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

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

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

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

思路

  • 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)$

则递推式为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)$

自顶向下动态规划

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)}$

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$为考虑考虑第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)$

则递推方程为

1
2
3
4
5
6
7
8
9
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)$最小者

则递推式有

1
2
3
4
5
6
7
8
9
10
11
12
13
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]$

则递推方程为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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的箭头指向相邻的较小元素,称在此排列中是移动的

减常量法

1
2
3
4
5
6
7
8
9
10
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$同序列中大于其的最小元素交换
  • 将新后缀颠倒,使其变为递增序列,加入列表中
1
2
3
4
5
6
7
8
9
10
11
12
13
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}$的子集之后

最小变化

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

  • 即每个位串和直接前趋之间仅仅相差一位
1
2
3
4
5
6
7
8
9
10
11
12
13
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个桶中情况数量

球同、桶不同、无空桶

  • 插板法

球同、桶不同、可空桶

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

球同、桶同、可空桶

  • 动态规划

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

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

球同、桶同、无空桶

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

球不同、桶同、无空桶

  • 第二类斯特林数

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

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

球不同、桶同、可空桶

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

球不同、桶不同、无空桶

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

球不同、桶不同、可空桶

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