What's the algorithm to get the highest number under a number?

Question

Ok, so... i have a list of numbers ranging from 0 to 1. Let's say the list is 20 items long for example:

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

How do i find the combination closest to average 0.5 and under average 0.5 consisting of 10 items?

My first attempt was sorting the list from high to low and then taking items 1 to 10 highest items and getting the average of them, if it was over 0.5, I would take item 2 to 11 and do the same until it was under 0.5.

This is not optimal because there might be scenarios where the best combination is a mix between some of the highest numbers and some of the lowest numbers

What is "highest combination"? Sum? Should the sum be closest under 0.5 or each of the used numbers? — Yunnosch, Feb 23 '20 at 20:48
Would you like to program this in javascript or in python? Which language did you use for your attempts? — Yunnosch, Feb 23 '20 at 20:49
Do you have any own attempt? E.g. just picking the first 10? Or maybe a brute force approach? What exactly is the specific programming problem you encountered while trying this yourself? — Yunnosch, Feb 23 '20 at 20:51

JohanC · Accepted Answer · 2020-02-24T00:40:57.657

The maximum is 0.4999988852755841 as the average of [0.3573617561804454, 0.07342389373929337, 0.9078793201337962, 0.6416645206383136, 0.3389149731962322, 0.27043204930306286, 0.9426831544676971, 0.5704199007458483, 0.5012058242125581, 0.3960034601385938].

As 20 choose 10 is only 184756, all combinations can be generated and summed quite easily.

The result comes from following Python code, but it could be converted to your programming language of choice. It runs in less than 1 tenth of a second.

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)

The problem is a version of the "knapsack" and the "subset sum problem" and is NP-complete. The linked Wikipedia pages give some approaches to find good approximate solutions.

PS: If you would allow combinations with replacement, the maximum would be 0.4999999625899948 for the combination [0.3573617561804454, 0.3573617561804454, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.5511799059130659, 0.6416645206383136, 0.5012058242125581, 0.46884307251796087, 0.46884307251796087]. This already takes 9 seconds to calculate with the Python code (20030010 combinations).

Maybe [this post](https://stackoverflow.com/a/47204248/12046409) to generate all combinations? — JohanC, Feb 24 '20 at 12:54

score -1 · Answer 2 · answered Feb 23 '20 at 21:22

-1

I'll try to answer your question and making an algorithm in python. Although you As I understand, you want to find the largest numeber that is less than 0.5.

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

You can also do this much simpler by using filter and max function.

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

answered Feb 23 '20 at 21:22

Alexander Nortung

85
2
6

The OP is not looking for that. They are looking for a *"combination"*... – trincot Feb 23 '20 at 21:25
I'm not looking for the largest number that is less than 0.5, i'm looking for the largest combination that has an average under 0.5 – Heine Elias Husdal Feb 23 '20 at 22:09

What's the algorithm to get the highest number under a number?

2 Answers2