状态压缩DP

状态压缩动态规划使用位运算来表示状态，适用于状态空间较大的问题。

旅行商问题

问题描述

给定一个图，找到访问所有城市恰好一次并回到起点的最短路径。

实现

def traveling_salesman(graph):
    n = len(graph)
    INF = float('inf')
    
    # dp[mask][u]: 访问过mask中的城市，最后到达u的最短路径
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 从城市0出发
    
    for mask in range(1, 1 << n):
        for u in range(n):
            if not (mask & (1 << u)):
                continue
            
            for v in range(n):
                if mask & (1 << v):
                    continue
                
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + graph[u][v])
    
    # 回到起点
    result = min(dp[(1 << n) - 1][u] + graph[u][0] for u in range(1, n))
    
    return result

# 示例图（邻接矩阵）
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

print("旅行商最短路径:", traveling_salesman(graph))  # 80

状态压缩背包

问题描述

在标准背包问题基础上，增加状态约束条件。

实现

def knapsack_with_state(items, capacity, max_state):
    n = len(items)
    
    # dp[i][c][s]: 前i个物品，容量c，状态s的最大价值
    dp = [[[-float('inf')] * (max_state + 1) for _ in range(capacity + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 0
    
    for i in range(1, n + 1):
        weight, value, state = items[i - 1]
        
        for c in range(capacity + 1):
            for s in range(max_state + 1):
                # 不选第i个物品
                dp[i][c][s] = dp[i - 1][c][s]
                
                # 选第i个物品
                if c >= weight and s >= state:
                    dp[i][c][s] = max(dp[i][c][s], dp[i - 1][c - weight][s - state] + value)
    
    return max(max(row) for row in dp[n][capacity])

# 示例
items = [
    (2, 3, 1),
    (3, 4, 2),
    (4, 5, 1)
]
capacity = 8
max_state = 3
print("状态压缩背包最大价值:", knapsack_with_state(items, capacity, max_state))  # 12

蒙德里安的梦想

问题描述

用 2x1 的多米诺骨牌覆盖 n x m 的棋盘，求方案数。

实现

def mondrian_dream(n, m):
    if n > m:
        n, m = m, n
    
    # 检查状态是否合法（没有连续的奇数个0）
    def is_valid(state):
        cnt = 0
        for i in range(m):
            if not (state & (1 << i)):
                cnt += 1
            else:
                if cnt % 2 == 1:
                    return False
                cnt = 0
        return cnt % 2 == 0
    
    # 预处理合法状态
    valid_states = [state for state in range(1 << m) if is_valid(state)]
    
    # 检查两个状态是否兼容
    def is_compatible(s1, s2):
        return (s1 & s2) == 0 and is_valid(s1 | s2)
    
    # 状态转移
    dp = [0] * (1 << m)
    dp[0] = 1
    
    for _ in range(n):
        new_dp = [0] * (1 << m)
        for s1 in valid_states:
            if dp[s1] == 0:
                continue
            for s2 in valid_states:
                if is_compatible(s1, s2):
                    new_dp[s2] += dp[s1]
        dp = new_dp
    
    return dp[0]

# 示例
print("蒙德里安方案数:", mondrian_dream(2, 3))  # 3

复杂度分析

问题	时间复杂度	空间复杂度
旅行商问题	O(n² 2^n)	O(n 2^n)
状态压缩背包	O(n C S)	O(C S)
蒙德里安的梦想	O(n 3^m)	O(2^m)

应用场景

• 旅行商问题
• 电路布线
• 资源分配问题