algorithm - 具有最小过冲的子集和变化 : find the subset that sums to >= target,

Question

给定一组正整数和一个目标总和 k，找到总和正好为 k 或最少超过 k 的子集。 (即相等或最小的过冲)

这个问题发生在现实生活中的业务功能请求中，预计集合大小通常在 1 到 30 之间。它必须在 3 秒内由低端 PC 解决，所以我估计一个暴力破解方法可能无法处理超过 10 个输入整数？

我查看了与子集总和和背包相关的搜索结果，但还没有看到有人讨论这个 >= 变体。

Answer 1

这是原始程序的一个相当简单的扩展:我们简单地使用动态规划算法，但如果这些超过原始值，我们也会存储我们生成的列表。

例如，我们可以实现这样的算法:

def least_gt_subset_sum(items, k):
    vals = [None]*(k+1)
    vals[0] = ()
    best_v = None
    best_k = 0
    for item in items:
        for i in range(k-1, -1, -1):
            if vals[i] is not None:
                if i + item <= k and vals[i+item] is None:
                    vals[i+item] = (*vals[i], item)
                if i + item > k and (best_v is None or i + item < best_v):
                    best_v = i + item
                    best_k = (*vals[i], item)
    if vals[k] is not None:
        return vals[k]
    else:
        return best_k

所以这里我们使用相同的技巧，但如果值高于k，我们会做一些簿记，并存储最好的结果。最后，我们查看是否有一个值完全匹配，如果没有，我们返回更高的最佳集合，否则我们返回准确的那个。