经典 NP 难问题详解
1.0-1 背包问题
问题描述：
给定一组物品，每个物品有自己的重量和价值，在限定的总重量内，我们需要选择其中若干个物品，使得所选物品的总价值最大。每个物品只能选择一次（0-1 选择）。
算法思想：
使用动态规划，通过构建一个二维数组来存储子问题的解，逐步递推得到最终结果。
动态规划解法步骤：
-
定义状态：$dp [i][w] $表示考虑前 i 个物品，背包容量为 w 时的最大价值。
-
状态转移方程：$dp [i][w] = max (dp [i-1][w], dp [i-1][w-weights [i-1]] + values [i-1])$，其中 $weights [i-1]$ 和 $values [i-1]$ 分别是第 i 个物品的重量和价值。
-
初始条件：$dp [0][w] = 0（$没有物品时），$dp [i][0] = 0$（背包容量为 0 时）。
-
最终结果：$dp [n][W]，$其中 n 是物品数量，W 是背包容量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def knapsack(weights, values, capacity):
n = len(weights)
# 创建二维数组dp
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# 填充dp数组
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
# 选择当前物品或不选择，取最大值
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
else:
# 当前物品重量超过背包容量，不能选择
dp[i][w] = dp[i-1][w]
# 返回最大价值
return dp[n][capacity]
# 示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity)) # 输出: 10
|
2.旅行商问题 (TSP)
问题描述：
给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短路径。
算法思想：
使用动态规划，通过状态压缩表示已访问的城市集合，递推计算从当前城市到终点的最短路径。
动态规划解法步骤：
-
定义状态：$dp [mask][i]$ 表示已访问城市集合为 mask，当前位于城市 i 时，回到起点的最短路径长度。
-
状态转移方程：$dp [mask][i] = min (dp [mask | (1 « j)][j] + dist [i][j])$，其中 j 是未访问的城市。
-
初始条件：$dp [(1 « n) - 1][i] = dist [i][0]$（所有城市都已访问，直接返回起点）。
-
最终结果：$dp [1][0]$（从起点开始，访问所有城市后回到起点的最短路径）。
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
|
def tsp(dist):
n = len(dist)
# dp[i][mask]表示从起点0出发，当前在城市i，已访问城市集合为mask时的最短路径长度
# mask是一个二进制数，第j位为1表示城市j已访问
dp = [[float('inf')] * (1 << n) for _ in range(n)]
# 初始化：从起点0出发，已访问起点0（mask=1），路径长度为0
dp[0][1] = 0
# 枚举所有可能的城市访问状态
for mask in range(1 << n):
# 遍历当前已访问的城市
for current_city in range(n):
# 如果当前城市不在已访问集合中，跳过
if not (mask & (1 << current_city)):
continue
# 尝试从未访问的城市中选择下一个要访问的城市
for next_city in range(n):
# 如果下一个城市已经访问过，跳过
if mask & (1 << next_city):
continue
# 计算新的访问状态（添加下一个城市）
new_mask = mask | (1 << next_city)
# 更新从当前城市到下一个城市的最短路径
dp[next_city][new_mask] = min(
dp[next_city][new_mask],
dp[current_city][mask] + dist[current_city][next_city]
)
# 找到访问完所有城市后，从最后一个城市返回起点的最短路径
ans = float('inf')
for city in range(n):
# 如果城市不是起点（因为已经访问了所有城市，所以mask是全1）
if city != 0:
# 计算从该城市返回起点的总路径长度
total_distance = dp[city][(1 << n) - 1] + dist[city][0]
ans = min(ans, total_distance)
return ans
# 示例
n = int(input())
dist = [list(map(int, input().split())) for _ in range(n)]
print(tsp(dist))
|
3.图着色问题
问题描述：
给定一个无向图，为每个顶点分配一种颜色，使得相邻顶点颜色不同，求所需的最少颜色数。
算法思想：
使用回溯法或动态规划，通过状态压缩表示已着色的顶点集合，递推计算着色方案数。
动态规划解法步骤：
- 定义状态：$dp [mask] $表示顶点集合为 mask 的子图的着色方案数。
- 状态转移方程：$dp [mask] = sum (dp [mask - subset])$，其中 subset 是 mask 的独立集（内部顶点互不相邻）。
- 初始条件：$dp [0] = 1$（空集只有一种着色方案）。
- 最终结果：找到最小的 k，使得 $dp [(1 « n) - 1] > 0$（所有顶点都已着色）。
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
|
def graph_coloring_dp(graph):
"""
使用动态规划解决图着色问题
参数:
graph: 邻接表表示的图，例如[[1,2], [0,2], [0,1]]表示三角形图
返回:
最少需要的颜色数
"""
n = len(graph)
if n == 0:
return 0
# 预处理所有独立集(使用位掩码表示)
independent_sets = []
for mask in range(1, 1 << n):
is_independent = True
for i in range(n):
if mask & (1 << i):
for neighbor in graph[i]:
if mask & (1 << neighbor):
is_independent = False
break
if not is_independent:
break
if is_independent:
independent_sets.append(mask)
# 初始化DP数组
dp = [float('inf')] * (1 << n)
dp[0] = 0 # 空集需要0种颜色
# 动态规划填表
for mask in range(1, 1 << n):
# 遍历所有独立子集
for subset in independent_sets:
if (mask & subset) == subset: # subset是mask的子集
dp[mask] = min(dp[mask], dp[mask ^ subset] + 1)
return dp[(1 << n) - 1]
# 测试用例
if __name__ == "__main__":
# 示例1: 三角形图(需要3种颜色)
graph1 = [[1, 2], [0, 2], [0, 1]]
print("三角形图最少需要颜色:", graph_coloring_dp(graph1)) # 应输出3
# 示例2: 二分图(需要2种颜色)
graph2 = [[1, 3], [0, 2], [1, 3], [0, 2]]
print("二分图最少需要颜色:", graph_coloring_dp(graph2)) # 应输出2
# 示例3: 单顶点图(需要1种颜色)
graph3 = [[]]
print("单顶点图最少需要颜色:", graph_coloring_dp(graph3)) # 应输出1
# 示例4: 不连通的两个顶点(需要1种颜色)
graph4 = [[], []]
print("两不连顶点最少需要颜色:", graph_coloring_dp(graph4)) # 应输出1
# 示例5: 4个顶点的环(需要2种颜色)
graph5 = [[1, 3], [0, 2], [1, 3], [0, 2]]
print("四顶点环最少需要颜色:", graph_coloring_dp(graph5)) # 应输出2
|
4.集合覆盖问题
问题描述：
给定一个全集 U 和若干子集 $S1, S2, …, Sn$，找到最小的子集集合，使得这些子集的并集等于 U。
算法思想：
使用贪心算法或动态规划，通过状态压缩表示已覆盖的元素集合，递推计算最小子集数。
动态规划解法步骤：
-
定义状态：$dp [mask]$ 表示覆盖元素集合为 mask 所需的最小子集数。
-
状态转移方程：$dp [mask] = min (dp [mask], dp [mask - subset] + 1)$，其中 subset 是某个子集覆盖的元素。
-
初始条件：$dp [0] = 0$（空集不需要任何子集覆盖）。
-
最终结果：$dp [(1 « m) - 1]$，其中 m 是全集 U 的元素个数。
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
|
def set_cover(universe, subsets):
m = len(universe)
# 将元素映射到索引
element_to_index = {element: i for i, element in enumerate(universe)}
# 将每个子集转换为位掩码
subset_masks = []
for subset in subsets:
mask = 0
for element in subset:
if element in element_to_index:
mask |= 1 << element_to_index[element]
subset_masks.append(mask)
# 动态规划求解
dp = [float('inf')] * (1 << m)
dp[0] = 0 # 空集不需要任何子集
for mask in range(1 << m):
if dp[mask] == float('inf'):
continue
for subset_mask in subset_masks:
new_mask = mask | subset_mask
dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
# 返回覆盖全集所需的最小子集数
return dp[(1 << m) - 1]
# 示例
universe = {1, 2, 3, 4, 5}
subsets = [
{1, 2, 3},
{2, 4},
{3, 4},
{4, 5}
]
print(set_cover(universe, subsets)) # 输出: 2
|
5.哈密尔顿回路问题
问题描述：
给定一个图，求一条经过每个顶点恰好一次，最后回到起点的路径。
算法思想：
使用动态规划或回溯法，通过状态压缩表示已访问的顶点集合，递推计算是否存在哈密尔顿回路。
动态规划解法步骤：
-
定义状态：$dp [mask][i]$ 表示已访问顶点集合为 mask，当前位于顶点 i 时，是否存在一条从起点到 i 的哈密尔顿路径。
-
状态转移方程：$dp [mask][i] = OR (dp [mask - {i}][j] AND graph [j][i])
$，其中 j 是 mask 中除 i 外的顶点。
-
初始条件：$dp [1 « i][i] = True$（只访问一个顶点）。
-
最终结果：$OR (dp [(1 « n) - 1][i] AND graph [i][0])$，其中 n 是顶点数，0 是起点。
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
|
def hamiltonian_cycle(graph):
n = len(graph)
# 初始化dp数组
dp = [[False] * n for _ in range(1 << n)]
# 初始条件：只访问一个顶点
for i in range(n):
dp[1 << i][i] = True
# 状态压缩DP
for mask in range(1 << n):
for i in range(n):
if not (mask & (1 << i)): # i不在mask中
continue
# 枚举mask中除i外的顶点j
for j in range(n):
if j == i:
continue
if mask & (1 << j) and graph[j][i] and dp[mask ^ (1 << i)][j]:
dp[mask][i] = True
break
# 检查是否存在哈密尔顿回路
for i in range(1, n): # 起点为0，检查其他顶点到0是否有边
if dp[(1 << n) - 1][i] and graph[i][0]:
return True
return False
# 示例
graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0]
]
print(hamiltonian_cycle(graph)) # 输出: True
|
6.划分问题
问题描述：
给定一组正整数，是否可以将其分成两个子集，使得两个子集的元素和相等。
算法思想：
使用动态规划，将问题转化为子集和问题，判断是否存在一个子集的和等于总和的一半。
动态规划解法步骤：
-
定义状态：$dp [i][s] $表示考虑前 i 个元素，是否存在子集和为 s。
-
状态转移方程：$dp [i][s] = dp [i-1][s] OR dp [i-1][s-nums [i-1]]，其中 nums [i-1]$ 是第 i 个元素。
-
初始条件：$dp [0][0] = True$（空集的和为 0），$dp [0][s] = False（s>0）$。
-
最终结果：$dp [n][sum/2]$，其中 n 是元素个数，sum 是所有元素的和。
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
|
def can_partition(nums):
total_sum = sum(nums)
# 如果总和为奇数，无法平分
if total_sum % 2 != 0:
return False
target = total_sum // 2
n = len(nums)
# 创建dp数组
dp = [[False] * (target + 1) for _ in range(n + 1)]
# 初始条件
dp[0][0] = True # 空集的和为0
# 填充dp数组
for i in range(1, n + 1):
for s in range(target + 1):
# 不选择当前元素
dp[i][s] = dp[i-1][s]
# 选择当前元素
if s >= nums[i-1]:
dp[i][s] = dp[i][s] or dp[i-1][s-nums[i-1]]
return dp[n][target]
# 示例
nums = [1, 5, 11, 5]
print(can_partition(nums)) # 输出: True
|
7.SAT 问题描述
SAT（布尔可满足性问题）是计算机科学中的一个经典问题，也是第一个被证明为 NP 完全的问题。问题描述如下：
给定一个布尔表达式，判断是否存在一组变量赋值，使得整个表达式的值为真。布尔表达式通常以合取范式（CNF）的形式给出，即多个子句的合取（AND），每个子句是多个文字的析取（OR），文字是变量或其否定。
例如，下面是一个 $CNF$ 形式的布尔表达式：
1
|
(A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ D) ∧ (¬C ∨ ¬D)
|
解决思路
动态规划解决 SAT 问题的核心思想是通过状态转移来逐步构建解空间。对于 n 个变量的问题，我们可以考虑：
- 状态定义：定义 $dp [i][s]$ 表示考虑前 i 个变量，且子句集合状态为 s 时是否可满足
- 状态转移：对于每个变量，尝试赋值为真或假，然后更新子句的状态
- 边界条件：$dp [0][s]$ 表示不使用任何变量时，子句集合状态为 s 的可满足性
- 结果：$dp [n][all_satisfied]$ 表示所有变量都考虑后，所有子句是否都被满足
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
69
70
71
72
73
|
def sat_solver(clauses, variables):
"""
使用动态规划解决SAT问题
参数:
clauses: 列表，每个元素是一个子句，子句表示为文字列表，正文字为正数，负文字为负数
variables: 变量数量
返回:
是否存在满足所有子句的变量赋值
"""
# 预处理：计算每个子句的状态掩码
clause_masks = []
for clause in clauses:
mask = 0
for literal in clause:
var = abs(literal) - 1 # 变量索引从0开始
if literal > 0:
mask |= 1 << var # 正文字在对应位置为1
else:
mask |= 1 << (var + variables) # 负文字在高半部分对应位置为1
clause_masks.append(mask)
# 状态数量：每个变量可以为真或假
states = 1 << (2 * variables)
# dp[i][s]表示考虑前i个变量，子句状态为s时是否可满足
dp = [False] * states
dp[0] = True # 初始状态：没有变量，所有子句都未满足
# 遍历每个变量
for var in range(variables):
# 复制当前状态
new_dp = [False] * states
for s in range(states):
if not dp[s]:
continue
# 尝试将变量设为真
true_mask = 1 << var
new_state_true = s
for i, mask in enumerate(clause_masks):
if (mask & true_mask) and not (s & (1 << i)):
new_state_true |= 1 << i
# 尝试将变量设为假
false_mask = 1 << (var + variables)
new_state_false = s
for i, mask in enumerate(clause_masks):
if (mask & false_mask) and not (s & (1 << i)):
new_state_false |= 1 << i
new_dp[new_state_true] = True
new_dp[new_state_false] = True
dp = new_dp
# 检查是否所有子句都被满足
all_satisfied = (1 << len(clauses)) - 1
return dp[all_satisfied]
# 示例用法
if __name__ == "__main__":
# 示例：(A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ D) ∧ (¬C ∨ ¬D)
clauses = [
[1, -2, 3], # A ∨ ¬B ∨ C
[-1, 2, 4], # ¬A ∨ B ∨ D
[-3, -4] # ¬C ∨ ¬D
]
variables = 4
result = sat_solver(clauses, variables)
print("表达式是否可满足:", result)
|
这个实现使用了位掩码来表示子句的状态。对于每个变量，我们尝试将其赋值为真或假，然后更新子句的满足状态。状态转移的核心在于：
- 使用位掩码表示每个子句的满足条件
- 使用动态规划数组记录不同状态下的可满足性
- 对于每个变量，尝试两种赋值方式并更新状态
