Gặp gỡ ở giữa trong Java

Chúng tôi được cung cấp một mảng và một giá trị tổng; câu lệnh bài toán là tính tổng của tập hợp con tối đa không vượt quá giá trị tổng đã cho. Chúng tôi không thể áp dụng phương pháp brute force ở đây vì cấu trúc của mảng không giống với phương pháp chia và chinh phục.

Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -

Hãy để chúng tôi hiểu với ví dụ

Đầu vào - long arr [] ={21, 1, 2, 45, 9, 8} long given_Sum =12

Đầu ra −Tập hợp con tổng lớn nhất có tổng nhỏ hơn hoặc bằng tổng đã cho -> 12

Giải thích - Mảng được tách thành một tập hợp gồm 2 tập con. Cái đầu tiên có n / 2 phần tử và cái sau có phần còn lại. Tất cả các tổng của tập con có thể có của tập con đầu tiên được tính toán và lưu trữ trong mảng A và tương tự, tổng tập hợp con của tập con sau đó được tính và lưu trữ trong mảng B. Cuối cùng 2 bài toán con được hợp nhất sao cho tổng của chúng nhỏ hơn hoặc bằng thành số tiền đã cho.

Đầu vào - long arr [] ={2, 12, 16, 25, 17, 27} long given_Sum =24;

Đầu ra −Tập hợp con tổng lớn nhất có tổng nhỏ hơn hoặc bằng tổng đã cho -> 19

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Tạo một mảng kiểu dữ liệu dài và một biến kiểu dữ liệu dài và đặt nó thành 10. Gọi hàm là allowSubsetSum (arr, arr.length, given_Sum)).
Bên trong phương thức, allowSubsetSum (arr, arr.length, given_Sum))
- Gọi phương thức là giải_pháp_xuống (a, A, len / 2, 0) và giải_pháp_xuất_tỉnh (a, B, len - len / 2, len / 2)
- Tính kích thước của A và B rồi sắp xếp mảng B bằng phương thức sort ().
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước của một mảng A. hãy kiểm tra NẾU A [i] nhỏ hơn bằng với given_Sum rồi đặt get_lower_bound tocalculate_lower_bound (B, given_Sum - A [i]). Kiểm tra, NẾU get_lower_boundto size_B HOẶC B [get_lower_bound] không bằng (given_Sum - A [i])) thendecrement get_lower_bound bằng 1.
- Kiểm tra NẾU B [get_lower_bound] + A [i]) lớn hơn max rồi đặt max thành B [get_lower_bound] + A [i].
- trả về tối đa
Bên trong phương thức, giải quyết_mục_trục (long a [], long x [], int n, int c)
- Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn (1 <
- Bắt đầu vòng lặp FOR từ j đến 0 cho đến khi j nhỏ hơn n. Bên trong vòng lặp, kiểm tra IF i &(1 <
- Đặt x [i] thành tổng
Bên trong phương thức, allow_lower_bound (long a [], long x)
- Khai báo các biến từ trái sang -1 và từ phải sang chiều dài của mảng 1.
- Bắt đầu Vòng lặp WHILE sang trái + 1 ít hơn phải. Bên trong while, đặt m là (trái + phải)>>> 1. Kiểm tra NẾU a [m] lớn hơn x rồi đặt sang phải thành m.
- Khác, đặt sang trái thành m.
- Quay lại bên phải.

Ví dụ

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));
   }
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

The maximum sum subset having sum less than or equal to the given sum-->12