从 python 中的 int 列表生成加法组合

Question

我有一个长度未知的浮点数组。数字范围为 0-1000。我希望从那些小于用户定义值的数字中生成所有可能的加法组合，并将它们附加到另一个列表中。例如，如果 numlist =[200,350,510] 并且定义的最大值为 1200，我想生成组合：

200, 400(数列[1]*2+数列[2]*0+数列[3]*0), 600, 800, 1000, 1200, 350, 700(200*0+350*2 +510*0), 1050(200*0+350*0+510*2), 510, 1020, 550(200*1+350*1), 900(200*1+350*2) 等

该程序的目标是检查一个大的浮点数文件，并打印是否可以使用 numlist 中的数字构造单个浮点数。我认为最有效的方法是先找到所有组合，然后检查 float-combination==0 是否有系统或其他方法来执行此操作？ numlist 没有设置长度。

Answer 1

这是一个动态规划的例子：

def make_combo_dict(nums, max_):
    nums = sorted(set(nums))
    prev = {0: [""]}    # base state: no combinations
    for num in nums:
        nxt = defaultdict(list)
        for total, ways in prev.items():
            # k = 0
            nxt[total] = ways
            # k > 0
            max_k = (max_ - total) // num
            for k in range(1, max_k + 1):
                nxt[total + k*num].extend(
                    "{}{}{}*{}"
                    .format(way, " + " if way else "", k, num)
                    for way in ways
                )
        prev = nxt
    return prev

运行起来像

>>> combos = make_combo_dict([350, 200, 500, 510], 1200)

>>> for total,ways in sorted(combos.items()):
...     print("{:>4d}: {}".format(total, ", ".join(ways)))
   0: 
 200: 1*200
 350: 1*350
 400: 2*200
 500: 1*500
 510: 1*510
 550: 1*350 + 1*200
 600: 3*200
 700: 2*350
 710: 1*200 + 1*510
 750: 1*350 + 2*200
 800: 4*200
 850: 1*350 + 1*500
 860: 1*350 + 1*510
 900: 2*350 + 1*200, 2*200 + 1*500
 910: 2*200 + 1*510
 950: 1*350 + 3*200
1000: 5*200
1010: 1*500 + 1*510
1020: 2*510
1050: 3*350
1060: 1*350 + 1*200 + 1*510
1100: 2*350 + 2*200, 3*200 + 1*500
1110: 3*200 + 1*510
1150: 1*350 + 4*200
1200: 6*200, 1*200 + 2*500, 2*350 + 1*500

从 python 中的 int 列表生成加法组合

Generating addition combinations from an int list in python

python

combinations

addition