我有一个整数列表,我想将它们分成两个总和,使得它们的总和之间的差异最小:示例:输入 = [10,21,10,21,10]输出 = [41, 31]在这里我们可以将它们分组为(...
我有一个整数列表,我想将它们分成两个总和,使得它们的总和之间的差值最小:
例子:
input = [10,21,10,21,10]
output = [41, 31]
Here we can group them as (10,21,10), (21,10)
input = [1,2,3,4]
output = [5,5]
Groups are (1,4), (2,3)
限制:
input list size is 1 to 10^5
each item value in range 1 to 10^9
下面是我解决这个问题的代码:
public static List<Long> solve(List<Integer> nums) {
int totalSum = nums.stream().mapToInt(Integer::intValue).sum();
int n = nums.size();
boolean[][] dp = new boolean[n + 1][totalSum / 2 + 1];
// Initialize dp table
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= totalSum / 2; j++) {
dp[i][j] = dp[i - 1][j];
if (nums.get(i - 1) <= j) {
dp[i][j] |= dp[i - 1][j - nums.get(i - 1)];
}
}
}
// Find the closest sum to totalSum / 2
int sum1 = 0;
for (int j = totalSum / 2; j >= 0; j--) {
if (dp[n][j]) {
sum1 = j;
break;
}
}
long sum2 = totalSum - sum1;
return Arrays.asList(Math.max(sum1, sum2), Math.min(sum1, sum2));
}
public static void main(String[] args) {
System.out.println(solve(Arrays.asList(10, 21, 10, 21, 10))); // Output: [41, 31]
System.out.println(solve(Arrays.asList(10, 10, 10, 10))); // Output: [20, 20]
System.out.println(solve(Arrays.asList(5,3))); // Output: [5, 3]
System.out.println(solve(Arrays.asList(1,2,3,4))); // Output: [5, 5]
}
但我的限制是:
input list size is 1 to 10^5
each item value in range 1 to 10^9
所以 boolean[][] dp = new boolean[n + 1][totalSum / 2 + 1];
可能会导致内存不足错误。
解决这个问题的正确方法是什么?