python - 找到进入目标的最大数字，留下最小的余数

Question

我希望能够找到进入目标的最小数字。

例如:

target = 100
vals = [57, 71, 87, 97, 99, 101, 103, 113, 114, 115, 128, 129, 131, 137]

from itertools import combinations

def subsets_with_sum(lst, target, with_replacement=False):

    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

如果我要输入:

subsets_with_sum(vals, 270, False)

进入shell，我会输出:

[[57, 99, 114]]

但是，如果我要输入:

subsets_with_sum(vals, 239, False)

进入shell，我会输出:

[]

相反，我想输出进入目标的最大数字:[137, 101] 余数为 1。

有办法吗？

Answer 1

是的，有办法。

代替行:

        if t == sum(l): r.append(l)
        elif t < sum(l): return

您可能希望存储最好的结果，如下所示:

better = lambda x, y: x if sum (x) > sum (y) else y

def subsets_with_sum(lst, target, with_replacement=False):

    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t >= sum(l):
            r = better (r, l)
            for u in range(idx, len(lst)):
                r = better (r, _a(u + x, l + [lst[u]], r, t))
        return r
    return _a(0, [], [], target)

---

也就是说，如果值是小整数，您的问题(有和没有替换)是 knapsack problem 的情况，并且有一个使用动态规划的渐近更快的解决方案(请参阅链接)。