파티셔닝 알고리즘에서 하위 집합을 검색하는 방법은 무엇입니까?

Question

배열이 있는데 두 부분을 나누고 싶습니다. 예를 들어 [10, 30, 20, 50]의 합은 [10, 40] , [20, 30]으로 나눌 수 있습니다. 둘 다 합계가 50입니다. 이것은 본질적으로 파티셔닝 알고리즘이지만, 파티셔닝 가능 여부를 식별하는 것뿐만 아니라 서브 세트를 검색하고 싶습니다. 그래서, 내가 나서서 한 다음

업데이트 : 업데이트 스크립트가 중복

from collections import Counter 

def is_partitionable(a): 
    possible_sums = [a[0]] 
    corresponding_subsets = [[a[0]]] 
    target_value = sum(a)/2 
    if a[0] == target_value: 
     print("yes",[a[0]],a[1:]) 
     return 
    for x in a[1:]: 
     temp_possible_sums = [] 
     for (ind, t) in enumerate(possible_sums): 
      cursum = t + x 
      if cursum < target_value: 
       corresponding_subsets.append(corresponding_subsets[ind] + [x]) 
       temp_possible_sums.append(cursum) 
      if cursum == target_value: 
       one_subset = corresponding_subsets[ind] + [x] 
       another_subset = list((Counter(a) - Counter(one_subset)).elements()) 
       print("yes", one_subset,another_subset) 
       return 
     possible_sums.extend(temp_possible_sums) 
    print("no") 
    return 

is_partitionable(list(map(int, input().split()))) 

샘플 입력 & 출력을 처리하기 위해 :

>>> is_partitionable([10,30,20,40]) 
yes [10, 40] [30, 20] 
>>> is_partitionable([10,30,20,20]) 
yes [10, 30] [20, 20] 
>>> is_partitionable([10,30,20,10]) 
no 

나는 기본적으로 해당 값을 저장하고있어 추가 된 값은 corresponding_subsets입니다. 그러나 a의 크기가 증가함에 따라 corresponding_subsets에는 너무 많은 하위 목록 (possible_sums의 요소 수와 동일)이있을 것입니다. 이 작업을 더 효율적으로 할 수있는 방법이 있습니까?

Answer 1

여전히 어려운 문제이지만 다음을 시도해 볼 수 있습니다. 나는 n 요소가 있다고 가정하고 배열은 arr (1 기반 인덱싱이라고 가정)이라는 배열에 저장됩니다. 두 팀의 A과 B 두 팀을 구성하여 두 팀의 요소 합계가 같도록 팀 A과 B 사이에 arr의 요소를 분할하려고합니다. arr의 각 요소는 팀 A 또는 팀 B 중 하나를 선택할 수 있습니다. 요소 (i 번째 요소라고 함)가 팀 A으로 이동한다고 가정하면 -a[i]으로 표시하고 팀 B으로 이동하면 a[i]이되도록합니다. 따라서 각 요소를 팀에 할당 한 후 합계가 0이면 작업이 완료됩니다. 우리는 n 세트를 만들 것입니다 (그들은 중복을 저장하지 않습니다). 나는 arr = {10,20,30,40} 예제로 작업 할 것이다. 다음 단계

set_1 = {10,-10} # -10 if it goes to Team A and 10 if goes to B 

set_2 = {30,-10,10,-30} # four options as we add -20 and 20 

set_3 = {60,0,20,-40,-20,-60} # note we don't need to store duplicates 

set_4 = {100,20,40,-40,60,-20,-80,0,-60,-100} # see there is a zero means our task is possible 

에 따라 이제 i 번째 요소 a[i] 즉, a[i] 또는 -a[i]로 추가되었는지 확인하기 위해 마지막 세트에서 0에서 철수하기 만하면됩니다. 팀 A 또는 B에 추가됩니다.

편집

되돌아 루틴. 그래서 우리는 n을 set_1에서 set_n까지 설정합니다. 팀 A과 마찬가지로 list_B에 속하는 요소를 푸시하는 두 개의 목록 list_A을 만들자. 우리는 set_n부터 시작하여 변수 current_set을 초기에 값 n으로 사용합니다. 또한 마지막 목록에서 요소 0에 초점을 맞추고 있으므로 처음에는 값 0을 갖는 변수 current_element을 사용합니다. 아래의 코드에서 접근법을 따르십시오 (나는 모든 세트가 n으로 구성되어 있다고 가정합니다. 목록의 목록으로 쉽게 저장 했으므로 데이터 구조를 설정해야합니다). 또한 아래 코드는 0이 마지막 목록에있는 것으로 가정합니다. 우리의 임무가 가능합니다.

sets = [ [0], #see this dummy set it is important, this is set_0 
       #because initially we add -arr[0] or arr[0] to 0 
     [10,-10], 
     [30,-10,10,-30], 
     [60,0,20,-40,-20,-60], 
     [100,20,40,-40,60,-20,-80,0,-60,-100]] 

# my array is 1 based so ignore the zero 
arr = [0,10,20,30,40] 

list_A = [] 
list_B = [] 

current_element = 0 
current_set = 4 # Total number of sets in this case is n=4 

while current_set >= 1: 
    print current_set,current_element 
    for element in sets[current_set-1]: 
    if element + arr[current_set] == current_element: 
     list_B.append(arr[current_set]) 
     current_element = element 
     current_set -= 1 
     break 
    elif element - arr[current_set] == current_element: 
     list_A.append(arr[current_set]) 
     current_element = element 
     current_set -= 1 
     break 


print list_A,list_B 

Answer 2

이것은 실현 가능성에 대한 @ sasha 's algo의 구현입니다.

def my_part(my_list): 
    item = my_list.pop() 
    balance = [] 
    temp = [item, -item] 
    while len(my_list) != 0: 
     new_player = my_list.pop() 
     for i, items in enumerate(temp): 
      balance.append(items + new_player) 
      balance.append(items - new_player) 
     temp = balance[:] 
    balance = set(balance) 
    if 0 in balance: 
     return 'YES' 
    else: 
     return 'NO' 

나는 역 추적도하고 있습니다.