뺄셈을 사용한 부분 집합 합계 알고리즘

Question

조건을 더하거나 뺄 수있는 부분 집합 합계 문제가 있습니다. 나는 다섯 개 가지 측면이있는 경우 예를 들어, (1, 2, 3, 4, 5), 나는 7을 만들기 위해/I 추가 할 수있는 몇 가지 방법을 알고 조건을 빼기하려면 :

• 3 + 4
• + 2 + 4
• 5 2 + 5
• 1-2 + 4
• 등

파이썬에서 일부 코드를 작성하지만, 한 번 많은 용어가 매우 느립니다 :

import itertools 
from collections import OrderedDict 

sum_answer = 1 
terms = {"T1": 1, "T2": -2, "T3": 3, "T4": -4, "T5": 5} 
numlist = [v for v in terms.values()] 
zerlist = [x for x in itertools.repeat(0, len(numlist))] 
opslist = [item for item in itertools.product((1, -1), repeat=len(numlist))] 


res_list = [] 
for i in range(1, len(numlist)): 
    combos = itertools.combinations(numlist, i) 

    for x in combos: 
     prnlist = list(x) + zerlist[:len(numlist) - len(x)] 

     for o in opslist: 
      operators = list(o) 
      result = [] 
      res_sum = 0 

      for t in range(len(prnlist)): 
       if operators[t] == 1: 
        ops = "+" 
       else: 
        ops = "-" 
       if prnlist[t] != 0: 
        result += [ops, list(terms.keys())[list(terms.values()).index(prnlist[t])]] 
       res_sum += operators[t] * prnlist[t] 

      if sum_answer == res_sum: 
       res_list += [" ".join(result)] 

for ans in OrderedDict.fromkeys(res_list).keys(): 
    print(ans) 

백만 개의 중첩 루프가 굉장히 비효율적이라는 것을 알고 있습니다. 더 나은 알고리즘으로 속도를 높일 수있는 부분이 있습니까?

Answer 1

나는 당신의 아이디어가 대부분 옳다고 생각한다 : 용어의 각 조합을 생성하고 합계를 작성하여 히트 여부를 확인한다. 그래도 코드를 최적화 할 수 있습니다.

일단 문제가 발생하면 1 + 2을 생성하면 원하는 합계와 일치하지 않아 버리게됩니다. 그러나 4을 추가하면 해결책이됩니다. 합계를 처음부터 계산할 때 1 + 2 + 4을 생성 할 때까지는 해당 솔루션에 도달하지 못합니다. 또한 각 조합에 대해 처음부터 연산자를 추가 할 수있는 가능성을 생성합니다. 이는 동일한 이유로 많은 중복 작업을 수행합니다.

많은 목록 작업을 사용하므로 속도가 느려질 수 있습니다.

나는 이런 짓을 했을까 :

def solve(terms_list, stack, current_s, desired_s): 
    if len(terms_list) == 0: 
     if current_s == desired_s: 
      print(stack) 
     return 

    for w in [0, 1, -1]: # ignore term (0), add it (1), subtract it (-1) 
     stack.append(w) 
     solve(terms_list[1:], stack, current_s + w * terms_list[0], desired_s) 
     stack.pop() 

초기 호출은, 예를 들어, solve([1,2,3,4,5], [], 0, 7).

각 용어를 더하거나 뺄 수 있거나 무시할 수 있으므로이 값은 O(3^n) (일종의 읽기 전용)입니다.

재귀 호출이 terms_list 매개 변수의 복사본을 만들기 때문에 실제 구현의 복잡도는 O(n*3^n)입니다. 그러나 이것을 피할 수는 있지만 코드를 더 단순하게 만들고 운동으로 남겨두기를 원했습니다. 실제 표현식을 인쇄하기 전에 작성하지 않고 점진적으로 구성 할 수도 있지만, 더 많은 매개 변수가 필요할 수 있습니다.

그러나 아직까지 O(3^n)은 많은 부분이 많으므로 큰 경우 n과 상관없이 잘 수행하지 않아야합니다.

Answer 2

"일반"하위 집합 합계 문제와 비슷합니다. 문제를 해결하기 위해 DP을 사용하는 경우 여기에서 사용하지만 더 많은 가능성이 필요합니다. 추가하지 말고 현재 요소를 줄이십시오. 상향식 DP 용액을 번역 할 때

f(0,i) = 1    //successive subset 
f(x,0) = 0 x>0  //failure subset 
f(x,i) = f(x+element[i],i-1) + f(x-element[i],i-1) + f(x,i-1) 
           ^^^ 
       This is the added option for substraction 

, 넌 SUM 모든 요소들의 합이고 n 요소의 개수 크기 (SUM+1) * (2n+1)의 행렬을 생성 할 필요가있을 것이다.

Answer 3

지금 당장은 한 행의 필드 값 조합을 모두 허용 한 다음 (유효성 검사 - 다른 행과 비교하여 각 조합을 테스트합니다).

많은 데이터 행이 있다고 생각합니다. 행 (적어도 당신이 해결할 수있는 필드만큼 많은 수의 행)을 취하고 numpy.linalg.lstsq과 같은 대략적인 행렬 해석을 적용하여 이점을 활용할 것을 제안합니다.

이 중요한 장점이 있습니다

• 이 (당신의 모든 필드가 정수가 아닌 경우 필요)이 올바로 수행

• 가 쉽게 처리 할 수 ​​있습니다 반올림 오류 문제를 처리 할 수 ​​있습니다를 계수가 {-1, 0, 1}이 아닌 필드, 즉 계수가 비슷할 수있는 세율 0.12

• 은 디버깅 할 필요가없는 완전히 지원되는 코드를 사용합니다 N

• 이 높은 실행 최적화 된 코드를 사용합니다 상당히 빠른 (** 대부분 어떤 옵션에 따라 당신의 NumPy와는 컴파일 된)

• 는 (N 미친 듯이 더 나은 시간 복잡도 (O 같은 것을 가지고 * * 2.8)은 상당히 더 많은 필드 그래서

, 테스트 데이터로 확장한다 수단 대신 O (3 ** N)) 중 :

import numpy as np 

# generate test data 
def make_test_data(coeffs, mean=20.0, base=0.05): 
    w  = len(coeffs) # number of fields 
    h  = int(1.5 * w) # number of rows of data 
    rows = np.random.exponential(mean - base, (h, w)) + base 
    totals = data.dot(coeffs) 
    return rows.round(2), totals.round(2) 

,536,913,632 HTTP : 당신이 작업 솔루션을 가지고 있기 때문에 우리에게

>>> rows, totals = make_test_data([0, 1, 1, 0, -1, 0.12]) 

>>> print(rows) 
[[ 1.45 17.63 22.54 5.54 37.06 1.47] 
[ 11.71 80.43 26.43 18.48 11.08 8.8 ] 
[ 16.09 11.34 63.74 3.31 13.2 13.35] 
[ 11.96 12.17 10.23 8.15 73.3 0.42] 
[ 4.03 8.01 20.84 21.46 2.76 18.98] 
[ 3.24 6.6 35.06 23.17 9.03 8.58] 
[ 25.05 33.72 6.82 0.49 46.76 12.21] 
[ 70.27 1.48 23.05 0.69 31.11 43.13] 
[ 9.04 10.45 15.08 4.32 52.94 11.13]] 

>>> print(totals) 
[ 3.29 96.84 63.48 -50.85 28.37 33.66 -4.75 -1.4 -26.07] 

과 해석 코드 같은 것을 제공 10

,

>>> sol = np.linalg.lstsq(rows, totals) # one line! 

>>> print(sol[0])  # note the solutions are not *exact* 
[ -1.485730e-04 1.000072e+00 9.999334e-01 -7.992023e-05 -9.999552e-01 1.203379e-01] 

>>> print(sol[0].round(3))  # but they are *very* close 
[ 0. 1. 1. 0. -1. 0.12]