एल्गोरिदम एक निर्दिष्ट मान

Question

से अधिक पूर्णांक के संयोजन को खोजने के लिए एल्गोरिदम मैं एक एल्गोरिदम विकसित करने की कोशिश कर रहा हूं जो एक इनपुट सरणी लेता है और एक सरणी लौटाता है जैसे भीतर मौजूद पूर्णांक पूर्णांक के साथ पूर्णांक का संयोजन होता है एक निर्दिष्ट मूल्य से (आकार के के संयोजन तक सीमित)।

उदाहरण के लिए, यदि मेरे पास सरणी है [1,4,5,10,17,34] और मैंने न्यूनतम राशि 31 निर्दिष्ट की है, तो फ़ंक्शन [1,4,10,17] वापस आ जाएगा। या, अगर मैं चाहता हूं कि यह अधिकतम सरणी आकार 2 तक सीमित हो, तो यह केवल [34] वापस आ जाएगा।

क्या कोई कुशल ऐसा करने का तरीका है? किसी भी सहायता की सराहना की जाएगी!

Answer 1

ऐसा कुछ? यह मान देता है, लेकिन आसानी से अनुक्रम वापस करने के लिए अनुकूलित किया जा सकता है।

एल्गोरिदम: सॉर्ट किए गए इनपुट को मानते हुए, न्यूनतम से अधिक न्यूनतम राशि के लिए के-लंबाई संयोजनों का परीक्षण करें, न्यूनतम से अधिक पहले तत्व तत्व के बाद रोकें।

जावास्क्रिप्ट:

var roses = [1,4,5,10,17,34] 

function f(index,current,k,best,min,K) 
{ 
    if (roses.length == index) 
     return best 
    for (var i = index; i < roses.length; i++) 
    { 
     var candidate = current + roses[i] 
     if (candidate == min + 1) 
      return candidate 
     if (candidate > min) 
      best = best < 0 ? candidate : Math.min(best,candidate) 
     if (roses[i] > min) 
      break 
     if (k + 1 < K) 
     { 
      var nextCandidate = f(i + 1,candidate,k + 1,best,min,K) 
      if (nextCandidate > min) 
       best = best < 0 ? nextCandidate : Math.min(best,nextCandidate) 
      if (best == min + 1) 
       return best 
     } 
    } 
    return best 
} 

आउटपुट:

console.log(f(0,0,0,-1,31,3)) 
32 

console.log(f(0,0,0,-1,31,2)) 
34 

Answer 2

यह एक संकर समाधान के अधिक, गतिशील प्रोग्रामिंग और वापस ट्रैकिंग के साथ है। हम इस समस्या को हल करने के लिए अकेले बैक ट्रैकिंग का उपयोग कर सकते हैं, लेकिन फिर हमें समाधान खोजने के लिए संपूर्ण खोज (2^एन) करना है। डीपी भाग बैक ट्रैकिंग में खोज स्थान को अनुकूलित करता है।

import sys 
from collections import OrderedDict 
MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 
# Input part is over  

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

FoundSolution = False 
Solution  = [] 

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 
print sorted(Solution) 

नोट: सवाल, न्यूनतम राशि और अधिकतम सरणी आकार में आपके द्वारा दिए गए उदाहरण के अनुसार सख्ती से अधिक से अधिक और मान निर्दिष्ट क्रमश की तुलना में कम कर रहे हैं।

इस इनपुट के लिए

MinimumSum = 31 
MaxArraySize = 4 
InputData = sorted([1,4,5,10,17,34]) 

आउटपुट

[5, 10, 17] 

के रूप में, इस निवेश के लिए

MinimumSum = 31 
MaxArraySize = 3 
InputData = sorted([1,4,5,10,17,34]) 

आउटपुट

[34] 

वह जगह है जहाँ है

स्पष्टीकरण

Target  = MinimumSum + 1 
Previous, Current = OrderedDict({0:0}), OrderedDict({0:0}) 
for Number in InputData: 
    for CurrentNumber, Count in Previous.items(): 
     if Number + CurrentNumber in Current: 
      Current[Number + CurrentNumber] = min(Current[Number + CurrentNumber], Count + 1) 
     else: 
      Current[Number + CurrentNumber] = Count + 1 
    Previous = Current.copy() 

कार्यक्रम के इस भाग को इनपुट डेटा, अधिकतम संभव संख्या 1 से संख्याओं का योग करने के लिए आवश्यक से संख्या की न्यूनतम संख्या पाता है (जो सभी का योग है इनपुट डेटा)। Knapsack समस्या के लिए, यह एक गतिशील प्रोग्रामिंग समाधान है। आप इंटरनेट पर इसके बारे में पढ़ सकते हैं।

FoundSolution = False 
for Number, Count in Previous.items(): 
    if (Number >= Target and Count < MaxArraySize): 
     MaxArraySize = Count 
     Target  = Number 
     FoundSolution = True 
     break 

if not FoundSolution: 
    print "Not possible" 
    sys.exit(0) 
else: 
    print Target, MaxArraySize 

कार्यक्रम के इस भाग को, जो MaxArraySize मापदंड से मेल खाने Target मूल्य पाता है।

def Backtrack(CurrentIndex, Sum, MaxArraySizeUsed): 
    global FoundSolution 
    if (MaxArraySizeUsed <= MaxArraySize and Sum == Target): 
     FoundSolution = True 
     return 
    if (CurrentIndex == len(InputData) or MaxArraySizeUsed > MaxArraySize or Sum > Target): 
     return 
    for i in range(CurrentIndex, len(InputData)): 
     Backtrack(i + 1, Sum, MaxArraySizeUsed) 
     if (FoundSolution): return 
     Backtrack(i + 1, Sum + InputData[i], MaxArraySizeUsed + 1) 
     if (FoundSolution): 
      Solution.append(InputData[i]) 
      return 

Backtrack(0, 0, 0) 

अब हम जानते हैं कि समाधान मौजूद है, हम समाधान को फिर से बनाना चाहते हैं। हम यहां बैकट्रैकिंग तकनीक का उपयोग करते हैं। आप आसानी से इंटरनेट पर भी इसके बारे में बहुत अच्छे ट्यूटोरियल पा सकते हैं।