利用位屏蔽和动态规划解决最小代价任务分配问题 Bitmasking Dynamic Programming
利用位屏蔽和动态规划解决问题 Bitmasking & Dynamic Programming
位屏蔽基础
上一篇简单介绍了位屏蔽的赋值操作，在解决问题之前，再介绍一下位屏蔽的去值操作以及检查操作。
去值操作：
b & !(1 << i)
例子：
取i = 1， (1 << i) = 00010
!(1 << i) = 11101 (每位取反)
b = 01010
b & !(1 << i) = 01010 & 11101 = 01000 (1位上的值已经去除)
检查操作：
b & (1 << i)
例子：
取i = 1， (1 << i) = 00010
b = 01010
b & (1 << i) = 01010 & 00010 = 00010 (结果不为0) 则检查位上有值，即子级中包含检查的值。
利用位屏蔽和动态规划解决问题
题目：
需要给N个人分配总共N个任务，每个人完成一个任务，并且给出一个 N x N 的矩阵，cost[i][j] 代表第i个人完成第j个任务的代价。现在我们要找出分配任务代价最小的方案。
暴力解法：
assign(N, cost)
for i = 0 to N
assignment[i] = i
res = INFINITY
for j= 0 to factorial(N)
total_cost = 0
for i = 0 to N
total_cost = total_cost + cost[i][assignment[i]]
res = min(res, total_cost)
generate_next_greater_permutation(assignment)
return res
暴力解法会遍历所有的排布，然后返回最小代价的值。其时间复杂度是O(N!)。
接下来用位屏蔽和动态规划的思路来尝试解一下题目：
定义函数 dp=(k, mask)
k表示前k个人（任务0~k-1）已经被分配了任务，mask表示当前的屏蔽字。
在分配第k个任务时，动态寻找dp的过程中，状态方程是：
dp(k + 1, mask | (1 << i)) = min(dp(k + 1, mask | (1 << i)), dp(k, mask) + cost[k][i])
可以注意到， 上述方程中的k是屏蔽字中‘1’的数量（屏蔽字中，被置为一的个数为已经分配掉的任务的个数，和k的意义相同，因此上述方程可以简化为：
dp(mask | (1 << i)) = min(dp(mask | (1 << i), dp(mask) + cost[x][i] (x为mask内1的个数)
因此，解法如下：
assign(N, cost)
for i = 0 to power(2,N)
dp[i] = INFINITY
dp[0] = 0
for mask = 0 to power(2, N)
x = count_set_bits(mask)
for j = 0 to N
if jth bit is not set in i
dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + cost[x][j])
return dp[power(2, N) - 1]
上述的算法的时间复杂度是O(2nn) 空间复杂度是O(2n)。
如果你对算法中有任何地方没办法自行理解的，请在评论区说出疑问，我会尽我所能帮你理解！
本文参考 via hackerearth: dynamic-programming/bit-masking