Java 中的中间相遇
我们有一个数组和一个总和值;问题陈述是计算不超过给定总和值的最大子集和。我们不能在这里应用蛮力方法,因为给定数组的结构与分而治之方法不同。
让我们看看这个的各种输入输出场景 -
让我们通过例子来理解
输入 − long arr[] = { 21, 1, 2, 45, 9, 8 } long given_Sum = 12
输出 −和小于或等于给定和的最大和子集-->12
解释 −数组被分成一组 2 个子集。第一个有 n/2 个元素,后者有其余元素。计算第一个子集的所有可能子集和并将其存储在数组 A 中,类似地,计算后一个子集的子集和并将其存储在数组 B 中。最后合并 2 个子问题,使得它们的和小于或等于给定的和。
输入 − long arr[] = { 2, 12, 16, 25, 17, 27 } long given_Sum = 24;
输出 −总和小于或等于给定总和的最大总和子集-->19
解释 −数组被分成一组 2 个子集。第一个子集有 n/2 个元素,后者有其余元素。计算第一个子集的所有可能子集和并将其存储在数组 A 中,同样计算后一个子集的子集和并将其存储在数组 B 中。最后将 2 个子问题合并,使得它们的总和小于或等于给定的总和。
以下程序中使用的方法如下 −
创建一个 long 数据类型的数组和一个 long 数据类型的变量,并将其设置为 10。调用该函数作为 calculateSubsetSum(arr, arr.length, given_Sum))。
在方法内部,calculateSubsetSum(arr, arr.length, given_Sum))
调用该方法作为solve_subarray(a, A, len / 2, 0) 和solve_subarray(a, B, len - len / 2, len / 2)
计算 A 和 B 的大小,然后使用 sort() 方法对数组 B 进行排序。
从 i 到 0 开始循环 FOR,直到 i 小于数组 A 的大小。检查如果 A[i] 小于等于 given_Sum,则将 get_lower_bound 设置为 calculate_lower_bound(B, given_Sum - A[i])。检查,如果 get_lower_bound 等于 size_B 或 B[get_lower_bound] 不等于 (given_Sum - A[i])),则将 get_lower_bound 减 1。
检查 B[get_lower_bound] + A[i]) 是否大于 max,则将 max 设置为 B[get_lower_bound] + A[i]。
返回 max
在方法内部,solve_subarray(long a[], long x[], int n, int c)
从 i 到 0 开始循环,直到 i 小于 (1 << n)。在循环内部,将 sum 设置为 0。
从 j 到 0 开始循环,直到 j 小于 n。在循环中,检查 i & (1 << j)) 是否等于 0,然后将 sum 设置为 sum + a[j + c]。
将 x[i] 设置为 sum
在方法中,calculate_lower_bound(long a[], long x)
将变量声明为 left 为 -1,right 为数组 1 的长度。
开始循环,同时 left + 1 小于 right。在 while 中,将 m 设置为 (left + right) >>> 1。检查 a[m] 是否大于 x,然后将 right 设置为 m。
否则,将 left 设置为 m。
返回 right。
示例
import java.util.*; import java.lang.*; import java.io.*; public class testClass{ static long A[] = new long[2000005]; static long B[] = new long[2000005]; static void solve_subarray(long a[], long x[], int n, int c){ for (int i = 0; i < (1 << n); i++){ long sum = 0; for (int j = 0; j < n; j++){ if ((i & (1 << j)) == 0){ sum += a[j + c]; } } x[i] = sum; } } static long calculateSubsetSum(long a[], int len, long given_Sum){ solve_subarray(a, A, len / 2, 0); solve_subarray(a, B, len - len / 2, len / 2); int size_A = 1 << (len / 2); int size_B = 1 << (len - len / 2); Arrays.sort(B); long max = 0; for (int i = 0; i < size_A; i++){ if (A[i] <= given_Sum){ int get_lower_bound = calculate_lower_bound(B, given_Sum - A[i]); if (get_lower_bound == size_B || B[get_lower_bound] != (given_Sum - A[i])){ get_lower_bound--; } if((B[get_lower_bound] + A[i]) > max){ max = B[get_lower_bound] + A[i]; } } } return max; } static int calculate_lower_bound(long a[], long x){ int left = -1, right = a.length; while (left + 1 < right){ int m = (left + right) >>> 1; if (a[m] >= x){ right = m; } else{ left = m; } } return right; } public static void main(String[] args){ long arr[] = { 21, 1, 2, 45, 9, 8 }; long given_Sum = 12; System.out.println("The maximum sum subset having sum less than or equal to the given sum-->" + calculateSubsetSum(arr, arr.length, given_Sum)); } }
输出
如果我们运行上述代码,它将生成以下输出
The maximum sum subset having sum less than or equal to the given sum-->12