时间戳

首页 > 解决方案 > 子集总和变化：找到总和 >= 目标的子集，超调最小

algorithm - 子集总和变化：找到总和 >= 目标的子集，超调最小

问题描述

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

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

我已经查看了与子集总和和背包相关的搜索命中，但还没有看到有人讨论这个 >= 变化。

标签： algorithmdynamic-programming

解决方案

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

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

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

推荐阅读