बीच में जावा में मिलें

हमें एक सरणी और एक योग मूल्य प्रदान किया जाता है; समस्या कथन अधिकतम सबसेट योग की गणना करना है जो दिए गए योग मान से अधिक नहीं है। हम यहां ब्रूट फोर्स दृष्टिकोण लागू नहीं कर सकते क्योंकि दिए गए सरणी की संरचना डिवाइड और जीत दृष्टिकोण के समान नहीं है।

आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -

आइए उदाहरण से समझते हैं

इनपुट - लंबी गिरफ्तारी [] ={ 21, 1, 2, 45, 9, 8 } लंबे समय तक दिए गए_सम =12

आउटपुट −अधिकतम योग उपसमुच्चय दिए गए योग से कम या उसके बराबर है-->12

स्पष्टीकरण -सरणी 2 सबसेट के सेट में विभाजित है। पहले में n/2 तत्व होते हैं और बाद में शेष होते हैं। पहले उपसमुच्चय के सभी संभावित उपसमुच्चय की गणना और संग्रह ए में किया जाता है और इसी तरह बाद के उपसमुच्चय के उपसमुच्चय की गणना की जाती है और सरणी बी में संग्रहीत किया जाता है। अंत में 2 उप-समस्याओं को इस तरह मिला दिया जाता है कि उनका योग कम या बराबर हो दी गई राशि के लिए।

इनपुट - लंबी गिरफ्तारी [] ={ 2, 12, 16, 25, 17, 27 } लंबे समय तक दिए गए_सम =24;

आउटपुट −अधिकतम योग उपसमुच्चय दिए गए योग से कम या उसके बराबर है-->19

स्पष्टीकरण -सरणी 2 सबसेट के सेट में विभाजित है। पहले में n/2 तत्व होते हैं और बाद में शेष होते हैं। पहले उपसमुच्चय के सभी संभावित उपसमुच्चय की गणना और संग्रह ए में किया जाता है और इसी तरह बाद के उपसमुच्चय के उपसमुच्चय की गणना की जाती है और सरणी बी में संग्रहीत किया जाता है। अंत में 2 उप-समस्याओं को इस तरह मिला दिया जाता है कि उनका योग कम या बराबर हो दी गई राशि के लिए।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है -

• डेटा प्रकार लंबा और डेटा प्रकार का एक चर लंबा बनाएं और इसे 10 पर सेट करें। फ़ंक्शन को कैलकुलेटसबसेटसम (arr, arr.length, दिए गए_सम) के रूप में कॉल करें)।

• मेथड के अंदर, कैलकुलेटसबसेटसम(arr, arr.length, दिए गए_Sum))

  • विधि को हल_सुबरे (ए, ए, लेन / 2, 0) और हल_सुबरे (ए, बी, लेन - लेन / 2, लेन / 2) के रूप में कॉल करें

  • A और B के आकार की गणना करें और फिर सॉर्ट () विधि का उपयोग करके सरणी B को सॉर्ट करें।

  • I से 0 तक के लिए लूप प्रारंभ करें जब तक कि मैं एक सरणी A के आकार से कम नहीं हो जाता। यदि A [i] दिए गए_सम के बराबर से कम है तो चेक करें, फिर get_lower_bound tocalculate_lower_bound (B, दिए गए_Sum - A [i]) सेट करें। जांचें, अगर get_lower_boundto size_B या B[get_lower_bound] बराबर नहीं है (दिया गया_Sum - A[i])) तो get_lower_bound by 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 तक के लिए लूप प्रारंभ करें जब तक कि i से कम (1 <

  • j से 0 तक j से n से कम के लिए लूप प्रारंभ करें। लूप के अंदर, IF i &(1 <

  • x[i] को योग पर सेट करें

• मेथड के अंदर, कैलकुलेट_लोअर_बाउंड (लॉन्ग ए [], लॉन्ग एक्स)

  • वेरिएबल को बाएं से -1 और दाएं से लंबाई 1 की लंबाई के रूप में घोषित करें।

  • लूप प्रारंभ करें जबकि बाएँ + 1 दाएँ से कम। थोड़ी देर के अंदर, m को (बाएँ + दाएँ)>>> 1 के रूप में सेट करें। जाँचें कि क्या 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