我想得到一个算法,它为我提供基于子集的值的最佳近似值。
下面是一个例子:
N = 45
subset = [25,10,65,9,8]
output: [25,10,9]
重要的一点是算法必须给出最佳近似值(无论最终结果中的元素数量如何)。结果必须提供给出最接近的精确值的关联(但不能超过初始值)。你知道一种可以以最少的时间成本做到这一点的算法吗?
非常感谢您的帮助。
最佳答案
你不能在多项式时间内这样做(除非 P=NP)
找出是否存在总和恰好为 N 的子集显然比找到总和最接近 N 的子集容易,前一个问题称为 subset-sum已知是 NP 完全的。
然而,伪多项式时间是可能的。其实你的问题正好等于0/1 knapsack optimization problem如果我们取 subset
中的值是转换为背包的两个权重值。这个 0/1 背包问题有一个动态规划解决方案,运行于 O(nW)
哪里n
是 subset
中的项目数和 W
是目标,即 N
在你的代码中。
关于python - 找到一个值的子集的最佳近似值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64012231/