- 等和子数组最小和（Java JS Python）)
(100分)- 等和子数组最小和（Java & JS & Python）
题目描述
给定一个数组nums，将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值。
输入描述
第一行输入 m
接着输入m个数，表示此数组nums
数据范围：1<=m<=50, 1<=nums[i]<=50
输出描述
最小拆分数组和
用例
| 输入 | 7 4 3 2 3 5 2 1 |
| 输出 | 5 |
| 说明 | 可以等分的情况有： 4 个子集（5），（1,4），（2,3），（2,3） 2 个子集（5, 1, 4），（2,3, 2,3） 但最小的为5。 |
题目解析
题目要求我们求解最小拆分数组和，本质上就是寻找最小子集和，也就是确定最大的k值。因为k值越大，对应的子集和就越小。
k值的求解思路如下：
- 首先考虑k的上限。当数组所有元素相等时，k等于数组长度m，即每个元素都能独立构成一个子集。因此可以从k=m开始尝试。
- 如果k=m不满足条件，就逐步减小k值（k--），直到k=1为止。
- 验证数组能否划分为k个和相等的子集，就是判断nums是否能分成k个等和子集。
JavaScript算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { const m = parseInt(lines[0]); const arr = lines[1].split(" ").map(Number); console.log(getResult(arr, m)); lines.length = 0; } }); function getResult(arr, m) { const sum = arr.sort((a, b) => b - a).reduce((p, c) => p + c); while (m) { if (canPartitionMSubsets([...arr], sum, m)) return sum / m; m--; } return sum; } function canPartitionMSubsets(arr, sum, m) { if (sum % m !== 0) return false; const subSum = sum / m; if (subSum < arr[0]) return false; while (arr[0] === subSum) { arr.shift(); m--; } const buckets = new Array(m).fill(0); return partition(arr, 0, buckets, subSum); } function partition(arr, index, buckets, subSum) { if (index === arr.length) return true; const select = arr[index]; for (let i = 0; i < buckets.length; i++) { if (i > 0 && buckets[i] === buckets[i - 1]) continue; if (select + buckets[i] <= subSum) { buckets[i] += select; if (partition(arr, index + 1, buckets, subSum)) return true; buckets[i] -= select; } } return false; }Java算法源码
41行在用例
5
5 5 5 5 5
时会出现越界异常
import java.util.LinkedList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); LinkedList<Integer> link = new LinkedList<>(); for (int i = 0; i < m; i++) { link.add(sc.nextInt()); } System.out.println(getResult(link, m)); } public static int getResult(LinkedList<Integer> link, int m) { link.sort((a, b) -> b - a); int sum = 0; for (Integer ele : link) { sum += ele; } while (m > 0) { LinkedList<Integer> link_cp = new LinkedList<>(link); if (canPartitionMSubsets(link_cp, sum, m)) return sum / m; m--; } return sum; } public static boolean canPartitionMSubsets(LinkedList<Integer> link, int sum, int m) { if (sum % m != 0) return false; int subSum = sum / m; if (subSum < link.get(0)) return false; // while (link.get(0) == subSum) { // 此段代码可能越界 while (link.size() > 0 && link.get(0) == subSum) { link.removeFirst(); m--; } int[] buckets = new int[m]; return partition(link, 0, buckets, subSum); } public static boolean partition(LinkedList<Integer> link, int index, int[] buckets, int subSum) { if (index == link.size()) return true; int select = link.get(index); for (int i = 0; i < buckets.length; i++) { if (i > 0 && buckets[i] == buckets[i - 1]) continue; if (select + buckets[i] <= subSum) { buckets[i] += select; if (partition(link, index + 1, buckets, subSum)) return true; buckets[i] -= select; } } return false; } }Python算法源码
# 输入获取 m = int(input()) link = list(map(int, input().split())) # 算法入口 def getResult(link, m): link.sort(reverse=True) sumV = 0 for ele in link: sumV += ele while m > 0: if canPartitionMSubsets(link[:], sumV, m): return int(sumV / m) m -= 1 return sumV def canPartitionMSubsets(link, sumV, m): if sumV % m != 0: return False subSum = sumV / m if subSum < link[0]: return False while len(link) > 0 and link[0] == subSum: link.pop(0) m -= 1 buckets = [0] * m return partition(link, 0, buckets, subSum) def partition(link, index, buckets, subSum): if index == len(link): return True select = link[index] for i in range(len(buckets)): if i > 0 and buckets[i] == buckets[i - 1]: continue if select + buckets[i] <= subSum: buckets[i] += select if partition(link, index + 1, buckets, subSum): return True buckets[i] -= select return False # 算法调用 print(getResult(link, m))
