हमें एक सरणी और एक योग मान प्रदान किया गया है; समस्या कथन यह है कि अधिकतम उपसमुच्चय योग की गणना करें जो दिए गए योग मान से अधिक न हो। हम यहां ब्रूट फोर्स दृष्टिकोण लागू नहीं कर सकते क्योंकि दी गई सरणी की संरचना विभाजन और विजय दृष्टिकोण के समान नहीं है।
आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -
आइए उदाहरण से समझते हैं
इनपुट - long arr[] = { 21, 1, 2, 45, 9, 8 } long given_Sum = 12
आउटपुट - दिए गए योग से कम या बराबर अधिकतम योग वाला उपसमुच्चय --> 12
व्याख्या - सरणी को 2 उपसमुच्चय के सेट में विभाजित किया गया है। पहले में n/2 तत्व हैं और बाद वाले में शेष हैं। पहले उपसमुच्चय के सभी संभावित उपसमुच्चय योग की गणना की जाती है और सरणी A में संग्रहीत की जाती है और इसी तरह बाद वाले उपसमुच्चय के उपसमुच्चय योग की गणना की जाती है और सरणी B में संग्रहीत की जाती है। अंत में 2 उप-समस्याओं को इस तरह मिलाया जाता है कि उनका योग दिए गए योग से कम या बराबर हो।
इनपुट - long arr[] = { 2, 12, 16, 25, 17, 27 } long given_Sum = 24;
आउटपुट - दिए गए योग से कम या बराबर अधिकतम योग वाला उपसमुच्चय --> 19
व्याख्या - सरणी को 2 उपसमुच्चय के सेट में विभाजित किया गया है। पहले में n/2 तत्व हैं और बाद वाले में शेष हैं। पहले उपसमुच्चय के सभी संभावित उपसमुच्चय योग की गणना की जाती है और सरणी A में संग्रहीत की जाती है और इसी तरह बाद वाले उपसमुच्चय के उपसमुच्चय योग की गणना की जाती है और सरणी B में संग्रहीत की जाती है। अंत में 2 उप-समस्याओं को इस तरह मिलाया जाता है कि उनका योग दिए गए योग से कम या बराबर हो।
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है -
लॉन्ग डेटा प्रकार की एक सरणी और लॉन्ग डेटा प्रकार का एक वेरिएबल बनाएं और इसे 10 पर सेट करें। फ़ंक्शन को calculateSubsetSum(arr, arr.length, given_Sum)) के रूप में कॉल करें।
विधि के अंदर, calculateSubsetSum(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 के आकार से कम होने तक FOR लूप शुरू करें। जांचें IF A[i] दिए गए योग से कम या बराबर है तो get_lower_bound को calculate_lower_bound(B, given_Sum - A[i]) के रूप में सेट करें। जांचें, IF get_lower_bound size_B के बराबर है OR B[get_lower_bound] (given_Sum - A[i]) के बराबर नहीं है तो 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 तक i (1 << n) से कम होने तक FOR लूप शुरू करें। लूप के अंदर, sum को 0 पर सेट करें।
j से 0 तक j n से कम होने तक FOR लूप शुरू करें। लूप के अंदर, जांचें IF i & (1 << j)) 0 के बराबर है तो sum को sum + a[j + c] पर सेट करें।
x[i] को sum पर सेट करें
विधि के अंदर, calculate_lower_bound(long a[], long x)
चर घोषित करें जैसे left को -1 और right को सरणी 1 की लंबाई।
WHILE लूप शुरू करें left + 1 right से कम होने तक। व्हाइल के अंदर, m को (left + right) >>> 1 के रूप में सेट करें। जांचें IF 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
