Algorytm znajdowania kombinacji liczb całkowitych większych niż określona wartość

Question

Próbowałem opracować algorytm, który pobierałby tablicę wejściową i zwracał tablicę tak, że liczby całkowite w niej zawarte są kombinacją liczb całkowitych z najmniejszą sumą większą niż określona wartość (ograniczona do kombinacji o rozmiarze k).

Na przykład, jeśli mam tablicę [1,4,5,10,17,34] i podałem minimalną sumę 31, funkcja zwróci [1,4,10,17]. Lub, jeśli chciałbym, aby był ograniczony do rozmiaru maks. 2, po prostu wróciłby [34].

Czy istnieje sposób na wykonanie wydajnego? Każda pomoc będzie doceniona!

Answer 1

Coś takiego? Zwraca wartość, ale można ją łatwo dostosować do zwracania sekwencji.

Algorytm: przyjmując posortowane dane wejściowe, przetestuj kombinacje długości k dla najmniejszej sumy większej niż min, zatrzymaj po pierwszym elemencie tablicy większym niż min.

JavaScript:

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 
} 

wyjściowa:

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

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

Answer 2

To jest bardziej rozwiązanie hybrydowe, z programowania dynamicznego i algorytm z nawrotami. Możemy użyć Back Tracking samodzielnie, aby rozwiązać ten problem, ale wtedy musimy wykonać wyczerpujące wyszukiwanie (2^N), aby znaleźć rozwiązanie. Część DP optymalizuje przestrzeń poszukiwań w Back Tracking.

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) 

Uwaga: Zgodnie z przykładów podanych przez Ciebie w pytaniu, minimalną kwotę i maksymalną wielkość tablicy są ściśle większe i mniejsze niż wartości określone odpowiednio.

Do tego wejścia

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

Wyjście jest

[5, 10, 17] 

gdzie jak na tym wejściu

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

Wyjście jest

[34] 

Objaśnienie

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() 

Ta część programu wyszukuje minimalną liczbę numerów na podstawie danych wejściowych, wymagane, aby suma liczb od 1 do maksymalnej możliwej liczby (która jest sumą wszystkich dane wejściowe). Jest to rozwiązanie do programowania dynamicznego, w przypadku problemu z plecakiem. Możesz o tym przeczytać w Internecie.

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 

Ta część programu wyszukuje wartość Target który pasuje kryteria MaxArraySize.

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) 

Teraz, gdy wiemy, że istnieje rozwiązanie, chcemy odtworzyć rozwiązanie. Używamy techniki backtrackingu tutaj. Możesz łatwo znaleźć wiele dobrych tutoriali na ten temat również w Internecie.