题目描述
给定一个数组nums，可以将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，最大的平分组个数。
输入描述
- 第一行输入
- 接下来输入
个数，表示此数组
- 数据范围：
输出描述
最大的平分组个数
用例
用例1
--输入
7
4 3 2 3 5 2 1
--输出
4
--说明
可以等分的情况有
4个子集： (5) (1,4) (2,3) (2,3)
2个子集： (5, 1, 4) (2, 3, 2, 3)
最大的平分组数个数为 4 个用例2
--输入
9
5 2 1 5 2 1 5 2 1
--输出
4
--说明
可以等分的情况有
4 个子集 (5, 1) (5, 1) (5, 1) (2, 2, 2)
2 个子集 (5, 1, 5, 1) (2, 2, 2, 5, 1)
最大的平分组数个数为4个题目解析
直观理解，需要尽可能把数组进行分成若干组，并且保证 每组 元素和相等.
那么以数组 arr = [1, 1, 1, 1, 1] 为例，最多分成 5 组 ---> (1),(1),(1),(1),(1)
如何考虑解决该问题呢？
- 需要保证分组之后，每一组的元素之和都相同。那么很显然
- 每一组的元素和，最小 -- 不能小于数组中最小元素的值。
- 每一组的元素和，最大 -- 不能大于数组中所有元素的和。
- 最少也能分成一组，即所有元素分成一组。
- 假设数组长度为
n，那么最多分成n组（数组中所有元素都相同的情况下）
代码实现思路
- 令数组长度等于
n那么最多分为n组，最少分为1组（所有的元素分在一起） - 那么可以倒叙验证，目标数组是否可以等分为
i组，i = n,n-1,n-2,n-3......1依次递减 - 找到结果直接返回
- 那么现在问题变成了，验证一个数组是否能够等分为
i组 - 如何验证呢？
- 首先可以求得数组和
sum，已知需要分成k组，那么可以得到平均值average和 余数
- 如果余数不等于0，证明不能等分，直接跳过
- 然后对数组进行排序，如果
average < arr[n - 1]，证明同样不能等分 - 接下来如何解决呢？——————“动态规划”
- 数组中有
n个元素，那么就一共有1 << n个状态
- ex：如果选择了数组中的所有元素，那么对应的下标索引就是
(1 << n) - 1
show code
import java.util.Arrays;
import java.util.Scanner;
/**
* desc : <a href="https://fcqian.blog.csdn.net/article/details/128199836">最大平分数组</a>
* <p>
* create time : 2023/4/11 15:32
*/
public class MaxAverageArr {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()) {
int m = in.nextInt();
int[] arr = new int[m];
for(int i = 0;i < m;i++) {
arr[i] = in.nextInt();
}
//System.out.println("最大平分数组的个数是：" + maxCutArr(arr));
System.out.println("最大平分数组的个数是：" + maxCutArr1(arr));
}
}
private static int maxCutArr(int[] arr) {
// 假设数组和为 sum 最大分组方案肯定小于等于 sum 数组中每一个元素都需要用到
int sumArr = Arrays.stream(arr).sum();
int n = arr.length;
Arrays.sort(arr);
// 因为每一个子数组的和需要保证相等，并且元素越多越好，所以划分子数组的和越小，就意味着分组个数越多.
// 最多划分为 n 个子集，（数组内所有元素都相同的情况） 最少划分为1个子集，即没有办法划分的情况.
// 那么划分的子数组的和 应当是 从 1 -> sumArr
for (int i = n; i >= 1; i--) {
if(sumArr % i != 0) {
// 无法划分
continue;
}
// 判断能不能划分为 i 个子集
if(check(arr, i, sumArr)) {
return i;
}
}
return 1;
}
private static boolean check(int[] arr, int k, int all) {
int n = arr.length;
int average = all/k;
if(arr[n-1] > average) {
return false;
}
// 1 << n ：表示 1 << n 个状态，对应了元素被选择的情况
// ex：如果选择了所有的元素，那么 dp[n] == all
int[] dp = new int[1 << n];
// 初始化所有的元素的值都是 -1 表示尚未计算.
Arrays.fill(dp, -1);
// 初始化 dp[0] = 0 表示一个元素都没有选择.
dp[0] = 0;
for(int i = 0;i < (1 << n);i++) {
if(dp[i] == -1) {
continue;
}
for(int j = 0;j < n;j++) {
// dp[i] % average 表示当前选择的方案
// arr[j] 表示接下来要选择 arr[j] 进行添加
// 判断其是否大于 average ,如果大于，表示超过了平均值，跳过该方案.
if(dp[i] % average + arr[j] > average) {
break;
}
// 这里判断 arr[j] 是否已经被选择，如果没有选择，则考虑加入到当前状态 i 中.
if(((i >> j) & 1) == 0) {
// next：表示 当前状态 i 添加了 arr[j] 之后的状态.
int next = i + (1 << j);
// 如果 dp[next] 已经大于 0 了，表示当前状态已经计算过了，跳过这个状态的计算.
if(dp[next] > 0) {
continue;
}
// 计算 dp[next] 的值.
dp[next] = dp[i] + arr[j];
}
if(dp[(1 << n) - 1] == all) {
return true;
}
}
}
return dp[(1 << n) - 1] == all;
}
}