04.08_状压dp
状压 DP
问题描述
状态压缩动态规划是指用二进制数表示状态的动态规划。
常见的有旅行商问题、集合划分等。
通常用一个整数的二进制位表示元素的选择状态。
旅行商问题(TSP)
算法思想
- 定义dp[state][i]表示已访问城市集合为state且当前在城市i的最小代价
- 枚举下一个要访问的城市j
- 状态转移方程：dp[state | (1<<j)][j] = min(dp[state][i] + cost[i][j])
- 最终答案为dp[(1<<n)-1][end]
代码实现
int tsp(vector<vector<int>>& cost) {
int n = cost.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0; // 初始在城市0
// 枚举状态
for (int state = 1; state < (1 << n); state++) {
// 枚举当前城市
for (int i = 0; i < n; i++) {
if (!(state & (1 << i))) continue;
// 枚举下一个城市
for (int j = 0; j < n; j++) {
if (state & (1 << j)) continue;
int nextState = state | (1 << j);
dp[nextState][j] = min(dp[nextState][j],
dp[state][i] + cost[i][j]);
}
}
}
return dp[(1 << n) - 1][n-1];
}
public int tsp(int[][] cost) {
int n = cost.length;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
dp[1][0] = 0; // 初始在城市0
// 枚举状态
for (int state = 1; state < (1 << n); state++) {
// 枚举当前城市
for (int i = 0; i < n; i++) {
if ((state & (1 << i)) == 0) continue;
// 枚举下一个城市
for (int j = 0; j < n; j++) {
if ((state & (1 << j)) != 0) continue;
int nextState = state | (1 << j);
if (dp[state][i] != Integer.MAX_VALUE) {
dp[nextState][j] = Math.min(dp[nextState][j],
dp[state][i] + cost[i][j]);
}
}
}
}
return dp[(1 << n) - 1][n-1];
}
def tsp(cost: List[List[int]]) -> int:
n = len(cost)
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 初始在城市0
# 枚举状态
for state in range(1, 1 << n):
# 枚举当前城市
for i in range(n):
if not (state & (1 << i)): continue
# 枚举下一个城市
for j in range(n):
if state & (1 << j): continue
next_state = state | (1 << j)
dp[next_state][j] = min(dp[next_state][j],
dp[state][i] + cost[i][j])
return dp[(1 << n) - 1][n-1]
集合划分
算法思想
- 定义dp[state]表示状态为state的最优解
- 枚举state的子集sub
- 状态转移方程：dp[state] = min(dp[state], dp[state^sub] + cost[sub])
- 最终答案为dp[(1<<n)-1]
代码实现
int partition(vector<int>& nums) {
int n = nums.size();
vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
// 预处理每个子集的代价
vector<int> cost(1 << n);
for (int state = 0; state < (1 << n); state++) {
for (int i = 0; i < n; i++) {
if (state & (1 << i)) {
cost[state] += nums[i];
}
}
}
// 枚举状态
for (int state = 0; state < (1 << n); state++) {
// 枚举子集
for (int sub = state; sub; sub = (sub - 1) & state) {
if (dp[state^sub] != INT_MAX) {
dp[state] = min(dp[state], dp[state^sub] + cost[sub]);
}
}
}
return dp[(1 << n) - 1];
}
public int partition(int[] nums) {
int n = nums.length;
int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
// 预处理每个子集的代价
int[] cost = new int[1 << n];
for (int state = 0; state < (1 << n); state++) {
for (int i = 0; i < n; i++) {
if ((state & (1 << i)) != 0) {
cost[state] += nums[i];
}
}
}
// 枚举状态
for (int state = 0; state < (1 << n); state++) {
// 枚举子集
for (int sub = state; sub > 0; sub = (sub - 1) & state) {
if (dp[state^sub] != Integer.MAX_VALUE) {
dp[state] = Math.min(dp[state], dp[state^sub] + cost[sub]);
}
}
}
return dp[(1 << n) - 1];
}
def partition(nums: List[int]) -> int:
n = len(nums)
dp = [float('inf')] * (1 << n)
dp[0] = 0
# 预处理每个子集的代价
cost = [0] * (1 << n)
for state in range(1 << n):
for i in range(n):
if state & (1 << i):
cost[state] += nums[i]
# 枚举状态
for state in range(1 << n):
# 枚举子集
sub = state
while sub:
dp[state] = min(dp[state], dp[state^sub] + cost[sub])
sub = (sub - 1) & state
return dp[(1 << n) - 1]
时间复杂度分析
| 旅行商问题 | ||
| 集合划分 |
应用场景
- 旅行商问题
- 集合划分问题
- 状态压缩搜索
- 子集枚举
- 图的最小支配集
注意事项
- 状态表示方法
- 位运算技巧
- 状态转移正确性
- 内存限制
- 计算复杂度
阿里巴巴公司氛围 441人发布