0

我有一点问题，我有一组加起来为 X 的总和，如下所示：

答：i + j + k = X

B：t + z = X

C：z + z = X

D：j + j + k + k = X

这些总和可能或多或少，我在这里给出 4，但可能有 N 个。

我的求和数有限，例如我有

i 的 12 个，z 的 35 个，j 的 12 个，k 的 18 个，t 的 21 个

我需要的是一种算法，它将确定使用这些组合的最佳方式，以便我最终得到最完整的 X

所以在上面的例子中使用：

组合C的17个，组合B的1个，组合A的12个，总共30个X的和，72个被加数

比使用更糟糕：

组合 B 21 个，组合 C 7 个，组合 D 6 个，总共 34 个 X 和，使用了 80 个和数

编辑：

进一步解释

使用组合 B 的 21 将“花费” 21 t 和 21 z 给我们留下： i 的 12，z 的 14，j 的 12，k 的 18，t 的 0

使用组合 C 的 7 将“花费” z 的 14（因为它使用 z 的 2 个和数来实现）给我们留下：i 的 12、z 的 0、j 的 12、k 的 18、t 的 0

使用组合 D 的 6 将花费 j 的 12 和 k 的 12（因为它使用它们两次）给我们留下： i 的 12，z 的 0，j 的 0，k 的 6，t 的 0

我们不能再进行加起来为 X 的组合，因此算法结束。

4

1 回答 1

1

我写了一个程序来暴力破解这个问题。

对于您的示例数据，哪个作为最佳组合给出：

组合 A 1 个，组合 B 19 个，组合 C 7 个，组合 D 5 个，总共 32 个 X 和，75 个被加数

代码虽然不是那么整洁而且可能不正确：

# Consider encoding the states
#{i,j,k}
#{i,z}
#{z,z}
#{j,j,k,k}
#as
#          i   z   j   k
limits =  (21, 35, 12, 18)
sets   = [(1,0,1,1), #
          (1,1,0,0), #
          (0,2,0,0), #
          (0,0,2,2), #
          ]

from heapq import heappush, heappop

def sub(A,B): return tuple(x - y for x,y in zip(A,B))

H = [(0,limits,[0]*len(sets))]
B = []
#X = 0
while H:
    #X += 1
    C, available, counts = heappop(H)
    #if X%1000 == 0: 
    #print C, available, counts
    if not any(all(not x > 0 for x in sub(available, s)) for s in sets):
        E = -C, sum(available), available, counts
        if E not in B:
            #print "found:", E
            if len(B) > 0:
                #print "best:", B[0]
                pass
            heappush(B, E)
    for i,s in enumerate(sets):
        diff = sub(available, s)
        if all(x > 0 for x in diff):
            counts_ = counts[:]
            counts_[i] += 1
            E = (C+1, diff, counts_)
            if E not in H:
                heappush(H, E)

a,b,c,d = heappop(B)

print "%u of combination A, %u of combination B, and %u of combination C, %u of combination D, total %u sums of X, %u summands used" % tuple(d+[-a, sum(limits)-sum(c)])

编辑：

将修改后的问题输入该程序后，它会在 9 秒内生成：

组合A的11个，组合B的20个，组合C的7个，组合D的0个，总共38个X和，87个被加数

修改后问题的编码：

#         i  z  j  k  t
limits = (12,35,12,18,21)
sets   = [(1,0,1,1,0), # {i,j,k}
          (0,1,0,0,1), # {t,z}
          (0,2,0,0,0), # {z,z}
          (0,0,2,2,0), # {j,j,k,k}
          ]
于 2012-10-21T02:10:01.093 回答