javascript - 求一个数下最大的数的算法是什么？

Question

好吧，所以...我有一个从 0 到 1 的数字列表。假设该列表有 20 个项目长，例如:

[0.3573617561804454、0.07342389373929337、0.06378891650870389、0.5511799059130659、0.2149869017013486、0.90787932013 37962, 0.6416645206383136, 0.08612996915296112, 0.3389149731962322, 0.27043204930306286, 0.4394280879520357, 0.713912997660 1778, 0.9426831544676971, 0.5704199007458483, 0.7661935177777641, 0.5012058242125581, 0.3960034601385938, 0.113003405975115 27, 0.4640564412846996, 0.46884307251796087]

如何找到由 10 个项目组成的最接近平均值 0.5 且低于平均值 0.5 的组合？

我的第一次尝试是将列表从高到低排序，然后取出项目 1 到 10 个最高的项目并获取它们的平均值，如果超过 0.5，我会取出项目 2 到 11 并执行相同的操作，直到达到低于 0.5。

这不是最佳选择，因为在某些情况下，最佳组合可能是一些最高数字和一些最低数字的混合

Answer 1

最大值为0.4999988852755841作为 [0.3573617561804454, 0.07342389373929337, 0.9078793201337962, 0.6416645206383136, 0.3389149731962322, 0.27043204930306286, 0.9426831544676971, 0.5704199007458483, 0.5012058242125581, 0.3960034601385938] 的平均值.

由于 20 选择 10 只有 184756，所以所有组合都可以很容易地生成和求和。

结果来自以下 Python 代码，但它可以转换为您选择的编程语言。它的运行时间不到十分之一秒。

import itertools

p = [0.3573617561804454, 0.07342389373929337, 0.06378891650870389, 0.5511799059130659, 0.2149869017013486,
     0.9078793201337962, 0.6416645206383136, 0.08612996915296112, 0.3389149731962322, 0.27043204930306286,
     0.4394280879520357, 0.7139129976601778, 0.9426831544676971, 0.5704199007458483, 0.7661935177777641,
     0.5012058242125581, 0.3960034601385938, 0.11300340597511527, 0.4640564412846996, 0.46884307251796087]

max_s = 0
for comb in itertools.combinations(p, 10):
    s = sum(comb)
    if s < 5 and s > max_s:
        max_s = s
        max_comb = comb
print(max_s/10, max_comb)

问题是 "knapsack" 的一个版本和 "subset sum problem"并且是 NP 完全的。链接的维基百科页面提供了一些寻找良好近似解决方案的方法。

PS:如果允许替换组合，则最大值为 0.4999999625899948对于组合[0.3573617561804454, 0.3573617561804454, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.6416645206383136, 0.5012058242125581, 0.46884307251796087, 0.46884307251796087] 。使用 Python 代码计算已花费 9 秒(20030010 个组合)。