You are given an integer array nums
and an integer k
. You are asked to distribute this array into k
subsets of equal size such that there are no two equal elements in the same subset.
A subset’s incompatibility is the difference between the maximum and minimum elements in that array.
Return the minimum possible sum of incompatibilities of the k
subsets after distributing the array optimally, or return -1
if it is not possible.
A subset is a group integers that appear in the array with no particular order.
Example 1:
Input: nums = [1,2,1,4], k = 2 Output: 4 Explanation: The optimal distribution of subsets is [1,2] and [1,4]. The incompatibility is (2-1) + (4-1) = 4. Note that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.
Example 2:
Input: nums = [6,3,8,1,3,1,2,2], k = 4 Output: 6 Explanation: The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3]. The incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.
Example 3:
Input: nums = [5,3,3,6,3,3], k = 3 Output: -1 Explanation: It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.
Constraints:
1 <= k <= nums.length <= 16
nums.length
is divisible byk
1 <= nums[i] <= nums.length
Solution: TSP
dp[s][i] := min cost to distribute a set of numbers represented as a binary mask s, the last number in the set is the i-th number.
Init:
1.dp[*][*] = inf
2. dp[1 <<i][i] = 0, cost of selecting a single number is zero.
Transition:
1. dp[s | (1 << j)][j] = dp[s][i] if s % (n / k) == 0, we start a new group, no extra cost.
2. dp[s | (1 << j)][j] = dp[s][i] + nums[j] – nums[i] if nums[j] > nums[i]. In the same group, we require the selected numbers are monotonically increasing. Each cost is nums[j] – nums[i].
e.g. 1, 3, 7, 20, cost is (3 – 1) + (7 – 3) + (20 – 7) = 20 – 1 = 19.
Ans: min(dp[(1 << n) – 1])
Time complexity: O(2^n * n^2)
Space complexity: O(2^n * n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua class Solution { public: int minimumIncompatibility(vector<int>& nums, int k) { const int n = nums.size(); const int c = n / k; int dp[1 << 16][16]; memset(dp, 0x7f, sizeof(dp)); for (int i = 0; i < n; ++i) dp[1 << i][i] = 0; for (int s = 0; s < 1 << n; ++s) for (int i = 0; i < n; ++i) { if ((s & (1 << i)) == 0) continue; for (int j = 0; j < n; ++j) { if ((s & (1 << j))) continue; const int t = s | (1 << j); if (__builtin_popcount(s) % c == 0) { dp[t][j] = min(dp[t][j], dp[s][i]); } else if (nums[j] > nums[i]) { dp[t][j] = min(dp[t][j], dp[s][i] + nums[j] - nums[i]); } } } int ans = *min_element(begin(dp[(1 << n) - 1]), end(dp[(1 << n) - 1])); return ans > 1e9 ? - 1 : ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment