我有点问题,我有一组加起来为 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个,X共30个和,用了72个加数
比使用更糟糕:
B组合21个,C组合7个,D组合6个,X共34个和,用了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 的组合,因此算法结束。
最佳答案
我写了一个程序来暴力破解这个问题。
对于您的示例数据,最佳组合给出:
1 of combination A, 19 of combination B, and 7 of combination C, 5 of combination D, total 32 sums of X, 75 summands used
虽然代码不是那么整洁而且可能不正确:
# 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 秒内生成:
11 of combination A, 20 of combination B, and 7 of combination C, 0 of combination D, total 38 sums of X, 87 summands used
修改后问题的编码:
# 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/