জাভা মধ্যে মাঝখানে দেখা

আমরা একটি অ্যারে এবং একটি সমষ্টি মান প্রদান করা হয়; সমস্যা বিবৃতি হল সর্বাধিক উপসেট যোগফল গণনা করা যা প্রদত্ত যোগফলের মান অতিক্রম করে না। আমরা এখানে ব্রুট ফোর্স পদ্ধতি প্রয়োগ করতে পারি না কারণ প্রদত্ত অ্যারের গঠন বিভাজন এবং বিজয় পদ্ধতির মতো নয়।

আসুন এর জন্য বিভিন্ন ইনপুট আউটপুট পরিস্থিতি দেখি -

আসুন উদাহরণ দিয়ে বোঝা যাক

ইনপুট − long arr[] ={ 21, 1, 2, 45, 9, 8 } long given_sum =12

আউটপুট −প্রদত্ত যোগফলের থেকে কম বা সমান সমষ্টির সর্বোচ্চ যোগফল-->12

ব্যাখ্যা −অ্যারেটি 2টি উপসেটের একটি সেটে বিভক্ত। প্রথমটিতে n/2 উপাদান রয়েছে এবং পরবর্তীটিতে বাকি রয়েছে। প্রথম সাবসেটের সমস্ত সম্ভাব্য উপসেটের যোগফল গণনা করা হয় এবং থিয়ারে এ সংরক্ষণ করা হয় এবং একইভাবে পরবর্তী উপসেটের উপসেটের যোগফল গণনা করা হয় এবং অ্যারে বি-তে সংরক্ষণ করা হয়। অবশেষে 2টি উপ-সমস্যা এমনভাবে একত্রিত করা হয় যে তাদের যোগফল এর থেকে কম বা সমান হয় প্রদত্ত যোগফল।

ইনপুট − long arr[] ={ 2, 12, 16, 25, 17, 27 } long given_sum =24;

আউটপুট −প্রদত্ত যোগফলের থেকে কম বা সমান সমষ্টি সহ সর্বাধিক যোগফল উপসেট-->19

ব্যাখ্যা −অ্যারেটি 2টি উপসেটের একটি সেটে বিভক্ত। প্রথমটিতে n/2 উপাদান রয়েছে এবং পরবর্তীটিতে বাকি রয়েছে। প্রথম সাবসেটের সমস্ত সম্ভাব্য উপসেটের যোগফল গণনা করা হয় এবং থিয়ারে এ সংরক্ষণ করা হয় এবং একইভাবে পরবর্তী উপসেটের উপসেটের যোগফল গণনা করা হয় এবং অ্যারে বি-তে সংরক্ষণ করা হয়। অবশেষে 2টি উপ-সমস্যা এমনভাবে একত্রিত করা হয় যে তাদের যোগফল এর থেকে কম বা সমান হয় প্রদত্ত যোগফল।

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

• ডাটা টাইপ লং এবং ডাটা টাইপের ভেরিয়েবলের একটি অ্যারে তৈরি করুন এবং এটি 10 ​​এ সেট করুন। ফাংশনটিকে calculateSubsetSum(arr, arr.length, given_Sum)) হিসাবে কল করুন।

• পদ্ধতির ভিতরে, SubsetSum(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[i] দেওয়া_Sum-এর সমান হয় তাহলে চেক করুন তারপর get_lower_bound tocalculate_lower_bound(B, given_Sum - A[i]) সেট করুন। চেক করুন, যদি get_lower_boundto size_B বা B[get_lower_bound] এর সমান না হয় (given_Sum - A[i])) তারপর decrement get_lower_bound 1।

  • চেক করুন IF B[get_lower_bound] + A[i]) সর্বোচ্চ থেকে বড় তারপর সর্বোচ্চ সেট করুন B[get_lower_bound] + A[i]।

  • রিটার্ন সর্বোচ্চ

• পদ্ধতির ভিতরে, solve_subarray(long a[], long x[], int n, int c)

  • i থেকে 0 পর্যন্ত FOR লুপ শুরু করুন যতক্ষণ না i কম (1 <

  • স্টার্ট লুপ FOR j থেকে 0 থেকে j পর্যন্ত n থেকে কম। লুপের ভিতরে, IF i &(1 <

  • যোগফল x[i] সেট করুন

• পদ্ধতির ভিতরে, calculate_lower_bound(long a[], long x)

  • অ্যারে 1-এর বাম থেকে -1 এবং ডান থেকে দৈর্ঘ্য হিসাবে ভেরিয়েবল ঘোষণা করুন।

  • স্টার্ট লুপ যখন বামে + 1 ডান থেকে কম। কিছুক্ষণের মধ্যে, m হিসেবে সেট করুন (বাম + ডান)>>> 1. চেক করুন IF a[m] x এর থেকে বড় তারপর ডানে m সেট করুন।

  • অন্যথায়, বামে সেট করুন মি।

  • ডানে ফিরুন।

উদাহরণ

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