在 Java 中相遇
我们提供了一个数组和一个总和值；问题陈述是计算不超过给定总和值的最大子集总和。我们不能在这里应用蛮力方法，因为给定数组的结构与分治方法不同。
让我们看看这个的各种输入输出场景-
让我们用例子来理解
输入 −longarr[]={21,1,2,45,9,8}longgiven_Sum=12
输出 -总和小于或等于给定总和的最大总和子集-->12
说明 -数组被分成一组2个子集。第一个有n/2个元素，后者有其余的。计算第一个子集的所有可能子集和并将其存储在数组A中，类似地计算后一个子集的子集和并将其存储在数组B中。最后合并2个子问题，使得它们的和小于或等于给定的总和。
输入 -longarr[]={2,12,16,25,17,27}longgiven_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的大小。检查IFA[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。
检查IFB[get_lower_bound]+A[i])大于max然后将max设置为B[get_lower_bound]+A[i]。
返回最大值
在方法内部，solve_subarray(longa[],longx[],intn,intc)
从i到0开始循环FOR直到i小于(1<<n)。在循环内，将sum设置为0。
从j到0开始循环FOR，直到j小于n。在循环内，检查IFi&(1<<j))是否等于0，然后将sum设置为sum+a[j+c]。
设置x[i]为总和
在方法内部，calculate_lower_bound(longa[],longx)
将变量声明为从左到-1，从右到数组1的长度。
开始循环，同时向左+比右少1。在while内，将m设置为(left+right)>>>1.检查IFa[m]大于x然后将右设置为m。
否则，将左设置为m。
返回正确。
示例
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