python - 寻找进入目标的最大数，剩余最小的数

我想找到进入目标的最小数字。
例如：

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.
有办法吗？

最佳答案

是的，有办法。
而不是台词：

        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的情况，并且使用动态规划有一个渐近更快的解决方案（请参阅链接）。

关于python - 寻找进入目标的最大数，剩余最小的数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33592059/