algorithm - 找到使用求和组合的最佳方式，以有限数量的求和获得最大的和

我有点问题，我有一组加起来等于X的和，比如：
A: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，这样算法就结束了。

最佳答案

我写了一个程序来解决这个问题。
对于您的示例数据，作为最佳组合提供：
组合A的1，组合B的19，组合C的7，组合5
组合D，共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)])

编辑：
在将revisied问题输入此程序后，它将在9秒内生成：
组合A的11，组合B的20，组合C的7，组合C的0
组合D，共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}
          ]

关于algorithm - 找到使用求和组合的最佳方式，以有限数量的求和获得最大的和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12994056/