子集总和变化：找到总和为 >= 目标的子集，具有最小的过冲

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，我们会做一些簿记，并存储最佳结果。最后，我们查看是否有一个值完全匹配，如果没有，我们返回更高的最佳集合，否则我们返回精确的集合。