Какой алгоритм получения наибольшего числа под номером?

Question

Хорошо, так ... у меня есть список чисел в диапазоне от 0 до 1. Скажем, список состоит из 20 элементов, например:

[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]

Как мне найти комбинацию, ближайшую к среднему 0,5 и менее 0,5, состоящую из 10 элементов?

Моя первая попытка состояла в том, чтобы отсортировать список от высокого к низкому, а затем взять элементы с 1 по 10 самых высоких элементов и получить их среднее значение, если это было больше 0,5, я бы взял пункт 2-11 и делал бы то же самое, пока оно не было меньше 0,5.

Это не оптимально, потому что может быть сценарий ios, где лучшая комбинация представляет собой смесь между некоторыми из самые высокие числа и некоторые из самых низких чисел

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)

Проблема заключается в версии "рюкзак" и "проблема подмножества сумм" и NP-полный. На связанных страницах Википедии даются некоторые подходы для поиска хороших приближенных решений.

PS: Если вы разрешите комбинации с заменой, максимум будет 0.4999999625899948 для комбинации [0.3573617561804454, 0.3573617561804454, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.6416645206383136, 0.5012058242125581, 0.46884307251796087, 0.46884307251796087]. Это уже занимает 9 секунд для расчета с кодом Python (комбинации 20030010).

Answer 2

Я постараюсь ответить на ваш вопрос и составить алгоритм в python. Хотя вы, как я понимаю, вы хотите найти наибольшее число, которое меньше 0,5.

def largestLessThan(arr, constraint):
    largest = arr[0]
    for num in arr:
        if num > largest and num < constraint:
            largest = num
    return largest

Вы также можете сделать это намного проще, используя фильтр и функцию max.

def largestLessThan(arr, constraint):
    return max(filter(lambda x: x < constraint, arr))