資料結構
網路
關係資料庫管理系統 (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
