জাভাতে Meet-in-the-Middle অ্যালগরিদম

আমাদের একটি অ্যারে এবং একটি যোগফল মান দেওয়া আছে; সমস্যা হল দেওয়া যোগফল মানকে অতিক্রম না করে সর্বোচ্চ সাবসেট যোগফল নির্ণয় করা। আমরা ব্রুট ফোর্স পদ্ধতি প্রয়োগ করতে পারি না কারণ দেওয়া অ্যারের কাঠামো ডিভাইড অ্যান্ড কনকর পদ্ধতির মতো নয়।

উদাহরণ দিয়ে বুঝি

উদাহরণ ১

ইনপুট: 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

ব্যাখ্যা: একই পদ্ধতিতে অ্যারে দুটি অংশে ভাগ করে সাবসেট যোগফল গণনা করা হয় এবং মার্জ করা হয়।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• long টাইপের অ্যারে এবং long টাইপের ভেরিয়েবল নেওয়া হয়ে ১০ সেট করা হয়। calculateSubsetSum(arr, arr.length, given_Sum) ফাংশন কল করা হয়।
• calculateSubsetSum() মেথডের ভিতরে:
  • solve_subarray(a, A, len/2, 0) এবং solve_subarray(a, B, len - len/2, len/2) কল করা হয়
  • A এবং B অ্যারের আকার নির্ণয় করে B অ্যারেটি sort() মেথড দিয়ে সর্ট করা হয়
  • A অ্যারের আকার পর্যন্ত লুপ চালানো হয়। যদি A[i] <= given_Sum হয়, তবে get_lower_bound = calculate_lower_bound(B, given_Sum - A[i]) নির্ণয় করা হয়। যদি get_lower_bound == size_B বা B[get_lower_bound] != (given_Sum - A[i]) হয়, তবে get_lower_bound ১ কমানো হয়।
  • যদি B[get_lower_bound] + A[i] > max হয়, তবে max আপডেট করা হয়।
  • max ফেরত দেওয়া হয়।
• solve_subarray(long a[], long x[], int n, int c) মেথডে:
  • i=0 থেকে (1<
  • j=0 থেকে n-1 পর্যন্ত লুপে যদি (i & (1<
  • x[i] = sum সেট করা হয়।
• calculate_lower_bound(long a[], long x) মেথডে:
  • left = -1, right = a.length ডিক্লেয়ার করা হয়
  • while (left + 1 < right) লুপে m = (left + right) >>> 1 গণনা করা হয়। যদি 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