알고리즘 : 범위 내에서 머물 수있는 최적의 값 조합

Question

다음과 같은 수학 문제가 있습니다. 응용 프로그램에서 필요한 문제가 있습니다. 근사치와 반대로 최적의 솔루션을 찾는 효율적인 방법이 있는지 궁금합니다.

1. 나는 양수 값과 음수 값 목록이 있습니다.
2. 이들 값의 합계는 (x, y) 범위 내에 있습니다.
3. 나머지 값의 합계가 범위 내에 있도록 제거 할 수있는 최대 값 수를 알고 싶습니다.

예 :

Values: -10, -5, -2, 7, 9, 15 
Sum: 14 
Range: (10, 18) 

Eliminate -2 => SUM = 16 
Eliminate -5 => SUM = 21 
Eliminate 7 => SUM = 14 
Eliminate -10 => SUM = 24 
Eliminate 9 => SUM = 15 

(15)을 제거하여 만들 것이다 범위 밖에 SUM = 0. 5 값이 제거되었습니다.

반면에 15를 제거하고 -10, -5, -2를 제거하면 4 개의 값만 제거 할 수 있습니다.

나는 모든 가능한 조합을 시도한 알고리즘을 작성했지만 그 성능은 25 개 이상의 값을 갖게되면 빠르게 저하됩니다. 나는 100-200 값에 대해 10 분의 1 초의 결과가 필요합니다.

현재는 절대 값을 기준으로 작은 값에서 큰 값으로 정렬 한 다음 합계가 더 이상 범위에 포함되지 않을 때까지 하나씩 제거합니다. 물론, 이것이 항상 최적의 솔루션을 제공하지는 못합니다.

이것이이 질문 유형에 적합한 장소가 아니며 다른 포럼을 참조 할 수 있다면 도움이 될 것입니다.

Answer 1

내가 하나의 값 하나를 제거하는 대신 그래서 (내 의견을 참조하십시오.)

을 허용 모르겠어요있는 뒤쪽으로이 일을 유혹하고있어,의 누구의 합이 가장 작은 하위 목록을 찾을 수 있습니다 범위 안에!

subset sum problem은 np 완료이므로이 방법도 문제가됩니다. (귀하의 범위가 0 인 상황을 상상해보십시오.)

O (2 ^N/2)에서이 문제를 해결하는 알고리즘이 있습니다. 파이썬 코드를 조롱 하겠지만, 위키 백과 페이지는 도움이 될 것입니다. 특정 범위에서 가장 적은 수의 목록을 찾으려면 약간의 수정이 필요합니다.

본질적으로, 목록을 길이 N/2의 두 임의의 하위 목록으로 분할합니다 (목록에 N 개의 요소가있는 경우). 그런 다음 각 목록에서 모든 하위 집합을 생성하고 합계를 계산하십시오. (여기서는 하위 집합과 그 합을 사전에 저장하므로 어떤 숫자가 남았는지 알 수 있습니다. 가장 작은 것을 찾고 싶기 때문에 작은 합과 같은 합을 가진 모든 하위 집합도 제거 할 것입니다.) 이 목록을 정렬하고 해당 범위 내에서 합계를 모두 찾을 때까지 하나의 앞으로 및 뒤로 이동하십시오. 마지막으로 가장 적은 요소가 포함되어 있는지 확인하십시오. 당신이 한 최종 목록이 범위 내에있는 규칙을 위반 검진을이 question

편집을 체크 아웃 할 수있는 경우

은 : 여기에 몇 가지 파이썬입니다.이다 :

• 검증되지 않은

• 파이썬, 분명히

• 하지

을 리팩토링 절실히 필요로하는

최적하지만 내 생각은 너무 특히 빠른되지 일반적인 아이디어로, 가장 빠른 알고리즘 그쪽으로 너는 얻을 수있을거야. 더 빠른 개념을보고 싶습니다.

>>> from itertools import combinations, chain 
>>> 
>>> available = [-10, -5, -2, 7, 9, 15] 
>>> target = (10, 18) 
>>> 
>>> 
>>> 
>>> def powerset(iterable): # from https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements 
...  xs = list(iterable) 
...  # note we return an iterator rather than a list 
...  return chain.from_iterable(combinations(xs, n) for n in range(len(xs)+1)) 
... 
>>> 
>>> def getMinList(available, target): 
...  middleIndex = len(available)/2 
...  l1 = available[:middleIndex] 
...  l2 = available[middleIndex:] 
...  dict1 = {} 
...  dict2 = {} 
...  for subset in powerset(l1): # reverse so only the smallest subsets are used. 
...   total = sum(subset) 
...   if total not in dict1: 
...    dict1[total] = subset 
...  for subset in powerset(l2): 
...   total = sum(subset) 
...   if total not in dict2: 
...    dict2[total] = subset 
...  sortedDict1 = sorted(dict1.iteritems()) 
...  sortedDict2 = sorted(dict2.iteritems()) 
...  resultList =() 
...  minValues = middleIndex * 2 
...  for k1, v1 in sortedDict1: 
...   for k2, v2 in reversed(sortedDict2): 
...    sumOfSubsets = k1 + k2 
...    if sumOfSubsets <= target[1] and sumOfSubsets >= target[0]: 
...     newTuple = v1 + v2 
...     lenNewTuple = len(newTuple) 
...     if (lenNewTuple) < minValues: 
...      resultList = ((sumOfSubsets, newTuple)) 
...      minValues = lenNewTuple 
...  return resultList 
... 
>>> getMinList(available, target) 
(15, (15,)) 
>>> 
>>> target = (10, 10) 
>>> 
>>> getMinList(available, target) 
(10, (-5, 15)) 
>>> 
>>> target = (19, 22) 
>>> 
>>> getMinList(available, target) 
(22, (7, 15)) 

Answer 2

당신이 사용할 수있는 (메모이 제이션 통해 구현) 동적 프로그래밍을 사용하여 다음

class Memoize: 
    def __init__(self, f): 
     self.f = f 
     self.memo = {} 
    def __call__(self, *args): 
     if not args in self.memo: 
      self.memo[args] = self.f(*args) 
     return self.memo[args]   

def maxsubset(values, min_sum, max_sum): 
    target_range = range(min_sum, max_sum+1) 

    @Memoize 
    def maxsubsetsize(target_sum, current_value_index=len(values)-1): 
     if current_value_index < 0: 
      if target_sum == 0: 
       return 0 
      else: 
       return float("-inf") 

     withit = maxsubsetsize(target_sum - values[current_value_index], current_value_index-1) + 1 
     without = maxsubsetsize(target_sum, current_value_index-1) 
     return max(withit, without) 

    result_sum = max(target_range, key=maxsubsetsize) 
    setsize = maxsubsetsize(result_sum) 

    result = [] 
    for i in reversed([x-1 for x in xrange(len(values))]): 
     s = maxsubsetsize(result_sum, i) 
     if s < setsize: 
      result.append(values[i+1]) 
      setsize -= 1 
      result_sum -= values[i+1] 

    return result 

사용법 : 특정 금액에 도달 할 경우

>>> values = [-10, -5, -2, 7, 9, 15] 
>>> min_sum = 10 
>>> max_sum = 18 

>>> xs = maxsubset(values, min_sum-sum(values), max_sum-sum(values)) 
>>> print xs 
[9, 7, -2, -5, -10] 
>>> print "sum:", sum(xs) 
-1 

당신은 추가 검사를 추가 할 수 있습니다 조금도. 사용 가능한 모든 음수 값은 합계에 대한 하한값을 제공하며 사용 가능한 모든 양수 값은 상한값을 제공합니다.

Answer 3

더 나쁜 경우에는 O (2^n) 인 모든 조합을 검사해야합니다. 그러나 가장 작은 하위 목록을 확인하기 시작하면 찾으면 중지 할 수 있습니다. 여기 내 C + +를 작성합니다. 메모리 사용량은 향상 될 수 있지만 더 많은 작업이 필요합니다. 입력에 따라 달라 지므로 매우 빠르거나 느릴 수 있습니다.

using namespace std; 

int compare(int x, int r1, int r2) 
{` 
    if (x < r1) return -1; 
    if (x > r2) return 1; 
    return 0; 
} 

// assume sorted v, binary search 
bool hasMemInRange(const vector<int>& v, int r1, int r2) 
{ 
    int b, e, c, r; 

    b=0; e=v.size(); 
    while(e > b) { 
     c = (b+e)/2; 
     r = compare(v[c], r1, r2); 
     if (r < 0) { 
      b += max(1, (e-b)/2); 
     } else if (r > 0) { 
      e -= max(1, (e-b)/2); 
     } else { 
      return true; 
     } 
    } 
    return false; 
} 
struct InputNode { 
    vector<int> l; 
    int   r1, r2; 
}; 

// assume v is sorted 
int maxRemoval(const vector<int>& v, int r1, int r2) 
{ 
    if (compare(0, r1, r2) == 0) return v.size(); 

    if (hasMemInRange(v, r1, r2)) return (v.size() - 1); 

    queue<InputNode> q; 
    InputNode node; 

    node.l = v; 
    node.r1 = r1; 
    node.r2 = r2; 
    q.push(node); 

    while(! q.empty()) { 
     InputNode& n = q.front(); 

     if (n.l.size() == 1) { 
      return 0; 
     } 

     for (int i=0; i<n.l.size(); ++i) { 
      vector<int> nv = n.l; 
      nv.erase(nv.begin() + i); 
      node.l = nv; 
      node.r1 = r1-n.l[i]; 
      if (hasMemInRange(nv, node.r1, node.r2)) { 
       return (nv.size() - 1); 
      } 
      q.push(node); 
     } 
     q.pop(); 
    } 
} 

int list_ints[] = {-10, -5, -2, 7, 9, 15 }; 

int main() 
{ 
    vector<int> l(list_ints, list_ints + sizeof(list_ints)/sizeof(int)); 

    for (auto i: list_ints) cout << i << " "; 
    cout << endl << endl; 

    cout << maxRemoval(l, 10, 18) << endl; 
    return 0; 
}