多子集和計算

Question

我有2組，集合A包含一組隨機數，集合B的元素是集合A的子集的和。

例如，

A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 

B = [183, 36, 231, 128, 137] 

我想找到哪個號碼是和它的像這樣的數據子集。

S = [[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 

我能用python寫出真正的笨蠻力代碼。

class SolvedException(BaseException): 
    pass 

def solve(sums, nums, answer): 
    num = nums[-1] 

    for i in range(0, len(sums)): 
     sumi = sums[i] 
     if sumi == 0: 
      continue 
     elif sumi - num < 0: 
      continue 
     answer[i].append(num) 

     sums[i] = sumi - num 

     if len(nums) != 1: 
      solve(sums, nums[:-1], answer) 
     elif sumi - num == 0: 
      raise SolvedException(answer) 

     sums[i] = sumi 

     answer[i].pop() 

try: 
    solve(B, A, [list() for i in range(0, len(B))]) 
except SolvedException as e: 
    print e.args[0] 

該代碼適用於小數據，但需要數十億年來計算我的數據（其中有71個數字和10個總和）。

我可以使用一些更好的算法或優化。

對不起，我英文不好，可怕的代碼效率不高。

---

編輯：對不起，我意識到我沒有準確地描述這個問題。

如A每一個元素都用來使B的elemens，sum(A) == sum(B)

此外，設置S必須設置A的分區。

Answer 1

這被稱爲子集和問題，它是一個衆所周知的NP完全問題。所以基本上沒有有效的解決方案。例如見https://en.wikipedia.org/wiki/Subset_sum_problem

但是如果您的號碼N不是太大，是一個僞多項式算法，採用動態規劃： 您閱讀列表中由左到右，並保持這是可行的和列表，並小於N.如果你知道對於一個給定的A可行的數字，你可以很容易地得到那些適用於A + [a]的數字。因此動態編程。它通常足夠快，可以解決您在那裏提供的大小問題。

這裏是一個Python的快速解決方案：

def subsetsum(A, N): 
    res = {0 : []} 
    for i in A: 
     newres = dict(res) 
     for v, l in res.items(): 
      if v+i < N: 
       newres[v+i] = l+[i] 
      elif v+i == N: 
       return l+[i] 
     res = newres 
    return None 

然後

>>> A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 
>>> subsetsum(A, 183) 
[15, 15, 33, 36, 39, 45] 

---

OP編輯後：

現在我理解正確的問題，我還是會覺得如果你有一個有效的子集和求解器，你的問題可以被有效地解決：我會使用分而治之的解決方案N於B：

• 切乙成兩個近似相等的塊B1和B2
• 使用子集 - 和求解器阿中搜索的所有子集（胡）的總和等於求和（B1）。
• 對於每個這樣的S：
  • 呼叫遞歸解決（S，B1）和解決（A - S，B2）
  • 如果兩個成功你有溶液

然而，我所建議的動態編程解決方案無法實現以下（71,10）問題。

---

順便說一句，這裏是一個使用分而治之的問題的快速解決方案不，但其中包含我的動態求解器的正確調整來獲取所有的解決方案：

class NotFound(BaseException): 
    pass 

from collections import defaultdict 
def subset_all_sums(A, N): 
    res = defaultdict(set, {0 : {()}}) 
    for nn, i in enumerate(A): 
     # perform a deep copy of res 
     newres = defaultdict(set) 
     for v, l in res.items(): 
      newres[v] |= set(l) 
      for v, l in res.items(): 
       if v+i <= N: 
        for s in l: 
         newres[v+i].add(s+(i,)) 
         res = newres 
         return res[N] 

def list_difference(l1, l2): 
    ## Similar to merge. 
    res = [] 
    i1 = 0; i2 = 0 
    while i1 < len(l1) and i2 < len(l2): 
     if l1[i1] == l2[i2]: 
      i1 += 1 
      i2 += 1 
     elif l1[i1] < l2[i2]: 
      res.append(l1[i1]) 
      i1 += 1 
     else: 
      raise NotFound 
      while i1 < len(l1): 
       res.append(l1[i1]) 
       i1 += 1 
       return res 

def solve(A, B): 
    assert sum(A) == sum(B) 
    if not B: 
     return [[]] 
     res = [] 
     ss = subset_all_sums(A, B[0]) 
     for s in ss: 
      rem = list_difference(A, s) 
      for sol in solve(rem, B[1:]): 
       res.append([s]+sol) 
       return res 

然後：

>>> solve(A, B) 
[[(15, 33, 39, 96), (36,), (8, 15, 60, 68, 80), (9, 46, 73), (45, 92)], 
[(15, 33, 39, 96), (36,), (8, 9, 15, 46, 73, 80), (60, 68), (45, 92)], 
[(8, 15, 15, 33, 39, 73), (36,), (9, 46, 80, 96), (60, 68), (45, 92)], 
[(15, 15, 73, 80), (36,), (8, 9, 33, 39, 46, 96), (60, 68), (45, 92)], 
[(15, 15, 73, 80), (36,), (9, 39, 45, 46, 92), (60, 68), (8, 33, 96)], 
[(8, 33, 46, 96), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (45, 92)], 
[(8, 33, 46, 96), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (45, 92)], 
[(9, 15, 33, 46, 80), (36,), (8, 15, 39, 73, 96), (60, 68), (45, 92)], 
[(45, 46, 92), (36,), (8, 15, 39, 73, 96), (60, 68), (9, 15, 33, 80)], 
[(45, 46, 92), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (9, 60, 68)], 
[(45, 46, 92), (36,), (15, 15, 60, 68, 73), (9, 39, 80), (8, 33, 96)], 
[(45, 46, 92), (36,), (9, 15, 15, 39, 73, 80), (60, 68), (8, 33, 96)], 
[(9, 46, 60, 68), (36,), (8, 15, 39, 73, 96), (15, 33, 80), (45, 92)]] 

>>> %timeit solve(A, B) 
100 loops, best of 3: 10.5 ms per loop 

所以它對於這個大小的問題是相當快的，雖然注意在這裏進行了優化。

Answer 2

一個完整的解決方案，計算所有的方式來完成。 我使用整數作爲速度和內存使用的特徵集：19='0b10011'代表[A[0],A[1],A[4]]=[8,9,33]這裏。

A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] 
B =[183, 36, 231, 128, 137] 

def subsetsum(A,N): 
    res=[[0]]+[[] for i in range(N)] 
    for i,a in enumerate(A): 
     k=1<<i   
     stop=[len(l) for l in res] 
     for shift,l in enumerate(res[:N+1-a]): 
      n=a+shift 
      ln=res[n] 
      for s in l[:stop[shift]]: ln.append(s+k) 
    return res 

res = subsetsum(A,max(B)) 
solB = [res[b] for b in B] 
exactsol = ~-(1<<len(A)) 

def decode(answer): 
    return [[A[i] for i,b in enumerate(bin(sol)[::-1]) if b=='1'] for sol in answer] 

def solve(i,currentsol,answer): 
     if currentsol==exactsol : print(decode(answer)) 
     if i==len(B): return 
     for sol in solB[i]: 
       if not currentsol&sol: 
        answer.append(sol) 
        solve(i+1,currentsol+sol,answer) 
        answer.pop() 

對於：比當兩個15不在同一子集

solve(0,0,[]) 

[[9, 46, 60, 68], [36], [8, 15, 39, 73, 96], [15, 33, 80], [45, 92]] 
[[9, 46, 60, 68], [36], [8, 15, 39, 73, 96], [15, 33, 80], [45, 92]] 
[[8, 15, 15, 33, 39, 73], [36], [9, 46, 80, 96], [60, 68], [45, 92]] 
[[9, 15, 33, 46, 80], [36], [8, 15, 39, 73, 96], [60, 68], [45, 92]] 
[[9, 15, 33, 46, 80], [36], [8, 15, 39, 73, 96], [60, 68], [45, 92]] 
[[15, 15, 73, 80], [36], [9, 39, 45, 46, 92], [60, 68], [8, 33, 96]] 
[[15, 15, 73, 80], [36], [8, 9, 33, 39, 46, 96], [60, 68], [45, 92]] 
[[45, 46, 92], [36], [15, 15, 60, 68, 73], [9, 39, 80], [8, 33, 96]] 
[[45, 46, 92], [36], [9, 15, 15, 39, 73, 80], [60, 68], [8, 33, 96]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [15, 33, 80], [9, 60, 68]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [60, 68], [9, 15, 33, 80]] 
[[45, 46, 92], [36], [8, 15, 39, 73, 96], [15, 33, 80], [9, 60, 68]] 
[[15, 33, 39, 96], [36], [8, 15, 60, 68, 80], [9, 46, 73], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 9, 15, 46, 73, 80], [60, 68], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 15, 60, 68, 80], [9, 46, 73], [45, 92]] 
[[15, 33, 39, 96], [36], [8, 9, 15, 46, 73, 80], [60, 68], [45, 92]] 
[[8, 33, 46, 96], [36], [15, 15, 60, 68, 73], [9, 39, 80], [45, 92]] 
[[8, 33, 46, 96], [36], [9, 15, 15, 39, 73, 80], [60, 68], [45, 92]] 

通告，該溶液被加倍。

它解決了獨特的解決方案的問題：在一秒鐘

A=[1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 
    1012, 1013, 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 
    1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033, 1034, 1035, 
    1036, 1037, 1038, 1039, 1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 
    1048, 1049] 

B=[5010, 5035, 5060, 5085, 5110, 5135, 5160, 5185, 5210, 5235] 

。不幸的是，它還不足以解決（71,10）問題。

另一個之一，在純動態規劃精神：

@functools.lru_cache(max(B)) 
def solutions(n): 
    if n==0 : return set({frozenset()}) #{{}} 
    if n<0 : return set() 
    sols=set() 
    for i,a in enumerate(A): 
      for s in solutions(n-a): 
       if i not in s : sols.add(s|{i}) 
    return sols 

def decode(answer): return([[A[i] for i in sol] for sol in answer]) 

def solve(B=B,currentsol=set(),answer=[]): 
    if len(currentsol)==len(A) : sols.append(decode(answer)) 
    if B: 
     for sol in solutions(B[0]): 
      if set.isdisjoint(currentsol,sol): 
       solve(B[1:],currentsol|sol,answer+[sol]) 

sols=[];solve()