지정된 값보다 큰 정수의 조합을 찾는 알고리즘

Question

나는 입력 배열을 취하여 그 안에 포함 된 정수가 가장 작은 합계가 더 큰 정수의 조합이되도록 알고리즘을 개발하려고 노력 해왔다. 지정된 값보다 큽니다 (크기가 k 인 조합으로 제한됨). I 배열 [1,4,5,10,17,34]이 I 및 31의 최소 합을 지정한 경우

는 예를 들어, 함수 반환 [1,4,10,17]. 또는 최대 배열 크기가 2로 제한 되길 원하면 [34]를 반환합니다.

이 작업을 수행 할 수있는 효율적인 방법이 있습니까? 어떤 도움을 주시면 감사하겠습니다!

Answer 1

이런 식으로 뭔가? 값을 반환하지만 시퀀스를 반환하도록 쉽게 조정할 수 있습니다.

알고리즘 : 정렬 된 입력을 가정하면, 분보다 작은 합에 대한 K 길이의 조합을 테스트 분보다 큰 첫 번째 배열 요소 후 멈춘다.

자바 스크립트 :

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

이 동적 프로그래밍 및 백 추적과 하이브리드 솔루션의 더 많은 것이다. 우리는이 문제를 해결하기 위해 Back Tracking 만 사용할 수 있지만 솔루션을 찾으려면 철저한 검색 (2^N)을 수행해야합니다. DP 부분은 뒤로 추적의 검색 공간을 최적화합니다.

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

출력이 입력

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

출력이

[34] 

같이

[5, 10, 17] 

이다

3,691,363,210

프로그램의이 부분은 모두의 합이다 (최대 가능한 수의 1 내지 수의 합계를 만들기 위해 요구되는 입력 데이터로부터 수의 최소 수를 발견

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 

프로그램의이 부분은 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) 

솔루션이 존재한다는 것을 알았으므로 이제 솔루션을 다시 만들고 싶습니다. 여기서 역 추적 기술을 사용합니다. 이것에 대한 좋은 자습서도 인터넷에서 쉽게 찾을 수 있습니다.