Minimum Incompatibility 最小不兼容性

问题描述：

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

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

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

子集的定义是数组中一些数字的集合，对数字顺序没有要求。

$k,nums.length范围[1,16],nums.length\mathrm{mod}k==0,nums[i]范围[1,nums.length]$

分析

$$<EmptyMathBlock>$$

问题要求把整数数组$nums$的$n$个元素平均分成$k$个组，而每个组就会有$n/k$个元素。

与此同时，根据题目，每个组会有一个$incompatibility$值，把$k$个组的$incompatibility$值累加得到$sum$，要求找到最小的$sum$。问题大概就是这么个意思。

$incompatibility$的值是由这一个组的$max-min$产生的。同时有限制不允许一个组有重复的元素。

所以理论上$incompatibility>0$。

首先很容易根据条件判断出哪种情况是不可能得到sum的。即$nums$中的某个元素次数$cnt[i]>k$,这样就无法满足组内元素不重复。

贪心策略?

到此就可以开始找了，朴素的想法，既然要最小，那么就让每个组最小这样就可以得到整体的最小。
那么第一步就是先排序，这样相邻的元素就会靠近，把相邻的满足条件的元素划分到一个组中，这样就可以得到最小了。
想法很好，但是并不能保证最终的结果是最小的。

也就是说简单的贪心策略并不能完全保证该策略的最终结果是最小的。

剩下的就只有暴力了，$m=n/k$,$m$为子集的大小，n最大可取$16$，所以$n$的所有非空子集数量就是$2^{16}-1$ ，即65535。
所以通过条件筛选出所有符合题意的子集。

• 满足 子集大小size==m，
• 满足 子集中不能有重复数字元素。

同时还可以将子集的$incompatibility$值计算出来。
到此每个子集都是符合条件的，剩下的就是把从X个子集中选出k个，并且他们的并集==$2^{16}-1$。

$$dfs(state)=\underset{sub\in U\setminus state}{\min }dfs(state\oplus sub)+map[sub]$$

代码

class Solution {int[] memo,map;int INF = 1<<30,u=0;public int minimumIncompatibility(int[] nums, int k) {int n = nums.length,max = 0;int[] cnt = new int[n+1];for(int num: nums){cnt[num]++;if(max<cnt[num]) max=cnt[num];if(max>k) return -1;}Arrays.sort(nums);memo = new int[1<<n];int m = n/k,state = 1;u = (1<<n)-1;map = new int[1<<n];for(;state<=u;state++){map[state] = memo[state] = -1;if(Integer.bitCount(state)!=m) continue; int curmin=16,curmax = 0,pre=-1;boolean dup =false;for(int i = 0;i<n;i++){if((state&(1<<i))==0) continue;if(pre==nums[i]){dup = true;break;}pre = nums[i];curmin= Math.min(curmin,nums[i]);curmax= Math.max(curmax,nums[i]);}if(dup) continue;map[state] = curmax-curmin;}return dfs(u);}public int dfs(int state){ if(state==0) return 0;if(memo[state]!=-1) return memo[state];int res = INF;for(int sub =state;sub>0;sub =(sub-1)&state){if(map[sub]==-1) continue; int nx = state^sub; int t = dfs(nx);res = Math.min(res,map[sub]+t);}        return memo[state]=res;}
}

时间复杂度$O(3^n)$

空间复杂度$O(2^n)$

Tag

Memoization
Bit Manipulation
Dynamic Programming
Bitmask