python - 找到一个值的子集的最佳近似值

Question

我想得到一个算法，它为我提供基于子集的值的最佳近似值。
下面是一个例子:

N = 45

subset = [25,10,65,9,8]

output: [25,10,9]

重要的一点是算法必须给出最佳近似值(无论最终结果中的元素数量如何)。结果必须提供给出最接近的精确值的关联(但不能超过初始值)。
你知道一种可以以最少的时间成本做到这一点的算法吗？
非常感谢您的帮助。

Answer 1

你不能在多项式时间内这样做(除非 P=NP)
找出是否存在总和恰好为 N 的子集显然比找到总和最接近 N 的子集容易，前一个问题称为 subset-sum已知是 NP 完全的。
然而，伪多项式时间是可能的。其实你的问题正好等于0/1 knapsack optimization problem如果我们取 subset 中的值是转换为背包的两个权重值。这个 0/1 背包问题有一个动态规划解决方案，运行于 O(nW)哪里n是 subset 中的项目数和 W是目标，即 N在你的代码中。