数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Java 中的中间相遇法
给定一个数组和一个和值，问题陈述是计算不超过给定和值的子集的最大和。我们不能在这里应用暴力方法，因为给定数组的结构与分治法不同。
让我们看看这个的各种输入输出场景 -
让我们用例子来理解
输入 - long arr[] = { 21, 1, 2, 45, 9, 8 } long given_Sum = 12
输出 - 最大子集和，其和小于或等于给定和 -> 12
解释 - 数组被分成两个子集。第一个包含 n/2 个元素，第二个包含其余元素。计算第一个子集的所有可能的子集和并将其存储在数组 A 中，类似地，计算第二个子集的子集和并将其存储在数组 B 中。最后，合并两个子问题，使得它们的和小于或等于给定和。
输入 - long arr[] = { 2, 12, 16, 25, 17, 27 } long given_Sum = 24;
输出 - 最大子集和，其和小于或等于给定和 -> 19
解释 - 数组被分成两个子集。第一个包含 n/2 个元素，第二个包含其余元素。计算第一个子集的所有可能的子集和并将其存储在数组 A 中，类似地，计算第二个子集的子集和并将其存储在数组 B 中。最后，合并两个子问题，使得它们的和小于或等于给定和。
下面程序中使用的方法如下：
创建一个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 开始循环，直到 i 小于数组 A 的大小。检查 IF A[i] 小于等于 given_Sum，然后设置 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 减 1。
检查 IF 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。在循环内，检查 IF i & (1 << j) 等于 0，则将 sum 设置为 sum + a[j + c]。
将 x[i] 设置为 sum
在方法 calculate_lower_bound(long a[], long x) 内部
声明变量 left 为 -1，right 为数组长度 1。
开始循环 WHILE left + 1 小于 right。在 while 循环内，将 m 设置为 (left + right) >>> 1。检查 IF 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
浏览量：290
