algorithm - 具有固定截止值的子阵列的最大总和

Question

我有一个整数列表，我需要找到一种方法来获取其中一个子集的最大总和，将元素添加到总数中，直到总和等于(或大于)一个固定的截止值。我知道这看起来与背包相似，但我不确定它是否等同。

对数组进行排序并添加最大元素直到 sum <= cutoff 不起作用。观察以下列表:

list = [6, 5, 4, 4, 4, 3, 2, 2, 1]
cutoff = 15

对于这个列表，以简单的方式计算结果总和为 15，这是非常次优的。据我所知，通过添加 4 + 4 + 4 + 2 + 6，使用此列表最多可以达到 20。如果这只是背包的不同版本，我可以实现一个背包解决方案，如我可能有足够小的列表来解决这个问题，但我更愿意做一些更有效率的事情。

Answer 1

首先，在任何求和中，最后添加最大元素不会产生更差的结果。因此，假设第一步将元素从小到大排序并没有什么坏处。

现在您使用类似于通常的子集求和的动态规划方法。

def best_cutoff_sum (cutoff, elements):
    elements = sorted(elements)
    sums = {0: None}
    for e in elements:
        next_sums = {}
        for v, path in sums.iteritems():
            next_sums[v] = path
            if v < cutoff:
                next_sums[v + e] = [e, path]
        sums = next_sums
    best = max(sums.keys())
    return (best, sums[best])

print(best_cutoff_sum(15, [6, 5, 4, 4, 4, 3, 2, 2, 1]))

通过一些工作，您可以将路径从当前的嵌套数组转换为您想要的任何格式。

如果你的非负元素列表有n个元素，你的cutoff是c，你的最大值是v，那么这个算法需要时间 O(n * (k + v))