时间戳

首页 > 解决方案 > 具有固定截止值的子数组的最大总和

algorithm - 具有固定截止值的子数组的最大总和

问题描述

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

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

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

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

标签： algorithm

解决方案

首先，无论如何，最后添加最大元素不会产生更差的结果。因此，第一步假设元素从最小到最大排序是没有害处的。

现在您使用类似于通常的子集总和的动态编程方法。

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元素，你的截止值是c并且你的最大值是v，那么这个算法将需要时间O(n * (k + v))

推荐阅读