दिलचस्प पोस्ट
कैसे जावास्क्रिप्ट के साथ स्क्रीन रिज़ॉल्यूशन का पता लगाने के लिए? एकाधिक कॉलम का उपयोग करते हुए पांडा डेटाफार्म कुल कार्य Google मानचित्र एपीआई V3: कैसे एक बिंदु ए से दिशा बी (ब्लू लाइन) की दिशा दिखाती है? सूचक संकेत क्षय और कार्यों को बहुआयामी सरणियों को पारित करने के लिए एंड्रॉइड स्पिनर त्रुटि: एंड्रॉइड.दृश्य.विंडो प्रबंधक $ BadTokenException: खिड़की जोड़ने में असमर्थ एंड्रॉइड के पूर्व 4.2 संस्करणों पर आरटीएल भाषाओं को कैसे प्रबंधित करें? जावास्क्रिप्ट / jQuery का उपयोग कर फ़ाइल डाउनलोड करें jQuery तालिका सॉर्ट अपाचे HTTP क्लाइंट SSLPeerUnverifiedException "Java.security.cert.CertificateException: कोई विषय वैकल्पिक नाम मौजूद नहीं" त्रुटि कैसे ठीक करें? कैसे System.IO.PathTooLongException से बचने के लिए? क्या नए एचटीएमएलएम्स तत्व हैं जैसे <section> और <आलेख> व्यर्थ? Directory.GetFiles (…) का उपयोग करते समय पथ तक पहुंच अस्वीकृत है दो फ़ील्ड को "अनूठा" जोड़े के रूप में कैसे परिभाषित करें XHR अनुरोध की प्रतिक्रिया के रूप में रिडायरेक्ट रिटर्निंग

एक विशेष मान के लिए सभी सबसेट्स का पता लगाएं

संख्याओं का एक सेट देखते हुए: {1, 3, 2, 5, 4, 9}, किसी विशेष मान की गणना के लिए सबसेट्स की संख्या को ढूंढें (कहें, इस उदाहरण के लिए 9)।

यह कम अंतर के साथ सबसेट राशि की समस्या के समान है, यह देखने के बजाय कि अगर सेट में 9 से लेकर एक सबसेट है, तो हमें इस तरह के सबसेट की संख्या पता लगानी होगी। मैं सबसेट राशि समस्या के समाधान के लिए यहां निम्नलिखित का अनुसरण कर रहा हूं। लेकिन और मैं सोच रहा हूं कि मैं कैसे इसे सबसेट की गिनती वापस करने के लिए संशोधित कर सकता हूं।

वेब के समाधान से एकत्रित समाधान "एक विशेष मान के लिए सभी सबसेट्स का पता लगाएं"

def total_subsets_matching_sum(numbers, sum): array = [1] + [0] * (sum) for current_number in numbers: for num in xrange(sum - current_number, -1, -1): if array[num]: array[num + current_number] += array[num] return array[sum] assert(total_subsets_matching_sum(range(1, 10), 9) == 8) assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4) 

व्याख्या

यह क्लासिक समस्याओं में से एक है विचार वर्तमान संख्या के साथ संभावित रकम की संख्या को खोजना है। और यह सच है कि, 0 का योग लाने का एक ही तरीका है। शुरुआत में, हमारे पास केवल एक नंबर है हम अपने लक्ष्य से शुरू करते हैं (समाधान में चर अधिकतम) और उस संख्या को घटाना यदि उस संख्या का योग प्राप्त करना संभव होता है (उस संख्या से संबंधित सरणी तत्व शून्य नहीं है) तो उसे वर्तमान संख्या से संबंधित सरणी तत्व में जोड़ें। कार्यक्रम इस तरह से समझना आसान होगा

 for current_number in numbers: for num in xrange(sum, current_number - 1, -1): if array[num - current_number]: array[num] += array[num - current_number] 

जब संख्या 1 है, तो केवल एक ही तरीका है जिसमें आप 1 के योग के साथ आ सकते हैं (1-1 बन जाता है और 0 से संबंधित तत्व 1 है)। तो सरणी इस तरह होगी (याद रखें कि तत्व शून्य में 1 होगा)

 [1, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

अब, दूसरी संख्या 2 है। हम 9 से 2 से घटाना शुरू करते हैं और इसकी वैध नहीं है (क्योंकि 7 का सरणी तत्व शून्य है, हम इसे छोड़ देते हैं) हम इसे 3 तक रखते हैं। जब इसकी 3, 3 – 2 1 और सरणी तत्व 1 से 1 के बराबर है और हम इसे 3 के सरणी तत्व में जोड़ते हैं। और जब इसकी 2, 2 – 2 बनती है 0 और हम 0 से 0 के सरणी तत्व से संबंधित मान हैं। इस पुनरावृत्ति के बाद सरणी इस तरह दिखती है

 [1, 1, 1, 1, 0, 0, 0, 0, 0, 0] 

जब तक हम सभी संख्याओं और सरणी को हर चलने के बाद इस तरह दिखते हैं, तब तक हम ऐसा करते रहते हैं

 [1, 1, 0, 0, 0, 0, 0, 0, 0, 0] [1, 1, 1, 1, 0, 0, 0, 0, 0, 0] [1, 1, 1, 2, 1, 1, 1, 0, 0, 0] [1, 1, 1, 2, 2, 2, 2, 2, 1, 1] [1, 1, 1, 2, 2, 3, 3, 3, 3, 3] [1, 1, 1, 2, 2, 3, 4, 4, 4, 5] [1, 1, 1, 2, 2, 3, 4, 5, 5, 6] [1, 1, 1, 2, 2, 3, 4, 5, 6, 7] [1, 1, 1, 2, 2, 3, 4, 5, 6, 8] 

अंतिम पुनरावृत्ति के बाद, हम सभी नंबरों पर विचार करेंगे और लक्ष्य प्राप्त करने के तरीकों की संख्या लक्षित मूल्य से संबंधित सरणी तत्व होगी। हमारे मामले में, अंतिम पुनरावर्तन के बाद आरे [9] 8 है।

आप गतिशील प्रोग्रामिंग का उपयोग कर सकते हैं एल्गो की जटिलता ओ (राशि * एन) है और ओ (योग) स्मृति का उपयोग करें

यहाँ सी # में मेरा कार्यान्वयन:

 private static int GetmNumberOfSubsets(int[] numbers, int sum) { int[] dp = new int[sum + 1]; dp[0] = 1; int currentSum =0; for (int i = 0; i < numbers.Length; i++) { currentSum += numbers[i]; for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--) dp[j] += dp[j - numbers[i]]; } return dp[sum]; } 

नोट : सबसेट्स की संख्या में मूल्य 2 ^ N हो सकता है क्योंकि यह आसान हो सकता है int प्रकार से अधिक होता है।

अॉगो केवल सकारात्मक संख्याओं के लिए काम करता है

यहां एक Java Solution :

यह एक शास्त्रीय बैक ट्रैकिंग समस्या है जो कि पूर्णांक सरणी के सभी संभावित सबसेट्स को खोजने के लिए है या सेट किया जाता है, जो कि इनपुट है और फिर उन को filtering हैं जो target दिए गए हैं

 import java.util.HashSet; import java.util.StringTokenizer; /** * Created by anirudh on 12/5/15. */ public class findSubsetsThatSumToATarget { /** * The collection for storing the unique sets that sum to a target. */ private static HashSet<String> allSubsets = new HashSet<>(); /** * The String token */ private static final String token = " "; /** * The method for finding the subsets that sum to a target. * * @param input The input array to be processed for subset with particular sum * @param target The target sum we are looking for * @param ramp The Temporary String to be beefed up during recursive iterations(By default value an empty String) * @param index The index used to traverse the array during recursive calls */ public static void findTargetSumSubsets(int[] input, int target, String ramp, int index) { if(index > (input.length - 1)) { if(getSum(ramp) == target) { allSubsets.add(ramp); } return; } //First recursive call going ahead selecting the int at the currenct index value findTargetSumSubsets(input, target, ramp + input[index] + token, index + 1); //Second recursive call going ahead WITHOUT selecting the int at the currenct index value findTargetSumSubsets(input, target, ramp, index + 1); } /** * A helper Method for calculating the sum from a string of integers * * @param intString the string subset * @return the sum of the string subset */ private static int getSum(String intString) { int sum = 0; StringTokenizer sTokens = new StringTokenizer(intString, token); while (sTokens.hasMoreElements()) { sum += Integer.parseInt((String) sTokens.nextElement()); } return sum; } /** * Cracking it up here : ) * * @param args command line arguments. */ public static void main(String[] args) { int [] n = {24, 1, 15, 3, 4, 15, 3}; int counter = 1; FindSubsetsThatSumToATarget.findTargetSumSubsets(n, 25, "", 0); for (String str: allSubsets) { System.out.println(counter + ") " + str); counter++; } } } 

यह उन सबसेटों के स्थान से अलग किए गए मूल्य प्रदान करता है जो एक लक्ष्य के लिए योग करते हैं।

{24, 1, 15, 3, 4, 15, 3} सेगेट्स के लिए कमेटा से अलग किए गए मानों को प्रिंट कर सकते हैं

1) 24 1

2) 3 4 15 3

3) 15 3 4 3

एक ही साइट geeksforgeeks भी एक विशेष मूल्य के लिए योग सब सबसेट आउटपुट के समाधान पर चर्चा: http://www.geeksforgeks.org/backttracking-set-4-subset-sum/

आपके मामले में, आउटपुट सेट के बजाय, आपको उन्हें गिनना चाहिए। एक ही पृष्ठ में अनुकूलित संस्करण की जांच सुनिश्चित करें, क्योंकि यह एक एनपी-पूर्ण समस्या है

यह सवाल भी पूछा गया है और इसका उल्लेख किए बिना स्टैक ओवरफ्लो में उत्तर दिया गया है कि यह एक सबसेट समस्या है: किसी दिए गए योग तक पहुंचने के लिए सभी संभव संयोजनों को ढूँढना

रूबी में यह मेरा कार्यक्रम यह सरणियों को वापस लौटाएगा, प्रत्येक ये उपलब्ध कराए गए लक्ष्यों के मूल्यों को प्रस्तुत करेगा।

 array = [1, 3, 4, 2, 7, 8, 9] 0..array.size.times.each do |i| @ary.combination(i).to_a.each { |a| print a if a.inject(:+) == 9} end 

मैंने इसे जावा द्वारा हल किया है यह समाधान काफी आसान है।

 import java.util.*; public class Recursion { static void sum(int[] arr, int i, int sum, int target, String s) { for(int j = i+1; j<arr.length; j++){ if(sum+arr[j] == target){ System.out.println(s+" "+String.valueOf(arr[j])); }else{ sum(arr, j, sum+arr[j], target, s+" "+String.valueOf(arr[j])); } } } public static void main(String[] args) { int[] numbers = {6,3,8,10,1}; for(int i =0; i<numbers.length; i++){ sum(numbers, i, numbers[i], 18, String.valueOf(numbers[i])); } } } 

सामान्य डीपी समाधान समस्या के लिए सच है।

एक ऑप्टिमाइज़ेशन जो आप कर सकते हैं, यह निर्धारित करना है कि वास्तविक सेट के बजाय किसी राशि के लिए कितने समाधान मौजूद हैं, जो उस योग को बनाते हैं …

जेएस में यह मेरा गतिशील प्रोग्रामिंग कार्यान्वयन यह सरणी की एक सरणी लौटाएगा, प्रत्येक, जो उपलब्ध कराए गए लक्ष्य मूल्य के लिए संक्षेप में प्रस्तुत करेगा।

 function getSummingItems(a,t){ return a.reduce((h,n) => Object.keys(h) .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n))) : m[k].map(sa => sa.concat(n)),m) : m, h), {0:[[]]})[t]; } var arr = Array(20).fill().map((_,i) => i+1), // [1,2,..,20] tgt = 42, res = []; console.time("test"); res = getSummingItems(arr,tgt); console.timeEnd("test"); console.log("found",res.length,"subsequences summing to",tgt); console.log(JSON.stringify(res));