เทคนิค Meet in the Middle ใน Java

ภาพรวมปัญหา

ได้รับอาร์เรย์และค่าเป้าหมาย (given_Sum) ต้องการหาผลรวมของชุดย่อย (subset sum) สูงสุดที่ไม่เกินค่าเป้าหมาย ไม่สามารถใช้ Brute Force ได้โดยตรงเพราะขนาดอาร์เรย์ใหญ่ จึงใช้เทคนิค Meet in the Middle (แบ่งปัญหาครึ่งๆ มารวมกัน)

ตัวอย่าง

ตัวอย่างที่ 1

Input: arr[] = { 21, 1, 2, 45, 9, 8 }, given_Sum = 12

Output: The maximum sum subset having sum less than or equal to the given sum → 12

ตัวอย่างที่ 2

Input: arr[] = { 2, 12, 16, 25, 17, 27 }, given_Sum = 24

Output: → 19

แนวทางการแก้ปัญหา

1. แบ่งอาร์เรย์เป็น 2 ส่วน: ส่วนแรก n/2 ตัว ส่วนที่สอง เหลืออีกส่วน
2. คำนวณผลรวมชุดย่อยทั้งหมดของแต่ละส่วน เก็บในอาร์เรย์ A และ B ตามลำดับ
3. เรียงลำดับอาร์เรย์ B
4. สำหรับแต่ละค่าใน A ที่ ≤ given_Sum:
   • หาค่าใน B ที่มากที่สุดแต่ไม่เกิน (given_Sum - A[i]) โดยใช้ Binary Search (lower bound)
   • อัปเดตค่าสูงสุด (max) หาก A[i] + B[j] ใหญ่กว่า
5. คืนค่า max

รายละเอียดฟังก์ชัน

• solve_subarray(a, x, n, c): สร้างผลรวมชุดย่อยทั้ง 2^n แบบ bitmask เก็บใน x
• calculate_lower_bound(a, x): Binary Search หาตำแหน่งแรกที่ a[m] ≥ x
• calculateSubsetSum(a, len, given_Sum): ฟังก์ชันหลักรวมขั้นตอนทั้งหมด

ตัวอย่างโค้ด Java

import java.util.*;

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