Thuật toán Meet in the Middle (Gặp nhau ở giữa) trong Java

Cho một mảng và một giá trị tổng. Bài toán là tìm tổng tập con lớn nhất không vượt quá giá trị tổng cho trước. Không thể áp dụng brute force vì cấu trúc mảng không phù hợp với chia để trị thông thường.

Ví dụ minh họa

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

Đầu ra: Tổng tập con lớn nhất ≤ tổng cho trước → 12

Giải thích: Mảng được chia thành 2 tập con. Tập đầu có n/2 phần tử, tập sau có phần còn lại. Tính tất cả tổng tập con của tập đầu lưu vào mảng A, tập sau lưu vào mảng B. Cuối cùng gộp 2 bài toán con sao cho tổng ≤ given_Sum.

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

Đầu ra: Tổng tập con lớn nhất ≤ tổng cho trước → 19

Giải thích: Tương tự chia mảng thành 2 nửa, tính tổng tập con cho mỗi nửa, sắp xếp và tìm cặp tối ưu.

Phương pháp tiếp cận

Tạo mảng long A[], B[] và gọi calculateSubsetSum(arr, arr.length, given_Sum)
Trong calculateSubsetSum:
- Gọi solve_subarray(a, A, len/2, 0) và solve_subarray(a, B, len-len/2, len/2)
- Tính kích thước A, B và sắp xếp mảng B
- Duyệt qua A, với mỗi A[i] ≤ given_Sum, tìm lower_bound trong B cho (given_Sum - A[i])
- Cập nhật max = max(max, B[lower_bound] + A[i])
- Trả về max
solve_subarray(a, x, n, c): Tạo tất cả tổng tập con của n phần tử bắt đầu từ chỉ số c
- Vòng lặp i từ 0 đến (1<<n)-1
- Vòng lặp j từ 0 đến n-1, nếu bit j của i là 0 thì cộng a[j+c] vào sum
- Lưu x[i] = sum
calculate_lower_bound(a, x): Tìm kiếm nhị phân lower_bound
- left = -1, right = a.length
- While left+1 < right: m = (left+right)>>>1, nếu a[m] >= x thì right=m else left=m
- Trả về right

Ví dụ mã Java

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

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