• 状态压缩

    假设有n个数，每个数有两种状态，用0和1表示。
    总共有状态压缩 - 图1种状态，用状态压缩 - 图2来表示。

    1. n = 16
    2. mask = 1 << n
    3. for s in range(mask):
    4.     for i in range(n):
    5.         if s & (1 << i):   # s & (1 << i)表明第i个数尚未使用
    6.             pass
    • 枚举子集

    对于二进制状态s，可以用如下方法枚举s子状态

    1. sub = s
    2. while sub:
    3.     sub = (sub - 1) & s

    时间复杂度：
    状态压缩 - 图3

    • 最小不兼容性

    给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。

    一个子集的 不兼容性 是该子集里面最大值和最小值的差。

    请你返回将数组分成 k 个子集后，各子集 不兼容性 的 和 的 最小值 ，如果无法分成分成 k 个子集，返回 -1 。

    子集的定义是数组中一些数字的集合，对数字顺序没有要求。
    来源：LeetCode
    链接：https://leetcode-cn.com/problems/minimum-incompatibility
    参考解答：(本解法容易超时)

    1. class Solution:
    2.     def minimumIncompatibility(self, nums: List[int], k: int) -> int:
    3.         n = len(nums)
    4.         if n == k:
    5.             return 0
    6.         m = n // k
    7.         dp = {}
    8.         for mask in range(1 << n):
    9.             bc = bin(mask).count('1')
    10.             if bc == m:
    11.                 used = set()
    12.                 flag = True
    13.                 for i in range(n):
    14.                     if mask & (1 << i):
    15.                         if nums[i] in used:
    16.                             flag = False
    17.                             break
    18.                         used.add(nums[i])
    19.                 if flag:
    20.                     dp[mask] = max(used) - min(used)
    21.             elif bc % m == 0:
    22.                 sub = mask
    23.                 while sub:
    24.                     if sub^mask in dp and sub in dp:
    25.                         if mask not in dp:
    26.                             dp[mask] = dp[sub^mask] + dp[sub]
    27.                         else:
    28.                             dp[mask] = min(dp[mask], dp[sub^mask] + dp[sub])
    29.                     sub = (sub - 1) & mask
    30.         return dp[(1 << n) - 1] if (1 << n) - 1 in dp else -1
    • 完成所有工作的最短时间

    给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

    请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

    返回分配方案中尽可能 最小 的 最大工作时间 。

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs
    参考解答：(本解法容易超时)
    状态压缩 - 图4

    1. class Solution:
    2.     def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
    3.         n = len(jobs)
    4.         dp = [[0] * (1 << n) for _ in range(k)]
    5.         for i in range(1 << n):
    6.             for j in range(n):
    7.                 if i & (1 << j):
    8.                     rest = i - (1 << j)
    9.                     dp[0][i] = dp[0][rest] + jobs[j]
    10.         for i in range(1, k):
    11.             for j in range(1 << n):
    12.                 s = j
    13.                 dp[i][j] = dp[0][j]
    14.                 while s:
    15.                     rest = j - s
    16.                     dp[i][j] = min(dp[i][j], max(dp[i-1][rest], dp[0][s]))
    17.                     s = (s - 1) & j
    18.         return dp[-1][(1<<n)-1]