Selecting max elements from list using input value Python

Question

I am building a program that selects max elements from a list which sums to a given input value

load_data = [1, 2, 3, 4, 10, 20]

eg user inputs 30 select 20 and 10 or user inputs 35 select 20, 10, 4 and 1since they are the possible largest elements that sum up to 30 or 35

code

def process(m): 
    print m


def selection():
    aux = range(len(load_data))
    global value  # <- value is the input 
    while aux and value > 0:
        posit = max(aux) >= value 
        index = aux[posit]
        elem = load_data[index]
        value = value - posit # <- subtract max value from input and repeat process 
        del aux[posit]  
        process(elem)

output always prints

this is not an easy task and i am not sure you understand its complexity (programmatically speaking). I cannot think of a way to do it that does not use recursion.. — Ma0
– Ma0, Commented Dec 2, 2016 at 12:37
You may find the following SO question helpful: stackoverflow.com/questions/3420937/… — dodell
– dodell, Commented Dec 2, 2016 at 12:50
Not straightforward. Linear programming might provide a solution? — Sanjay Manohar
– Sanjay Manohar, Commented Dec 2, 2016 at 13:19
The question may be related to the Knapsack problem. Have a look here and see if anything applicable? en.wikipedia.org/wiki/Knapsack_problem — Sanjay Manohar
– Sanjay Manohar, Commented Dec 2, 2016 at 13:25
For an input of 35, there is more than one answer. Consider @A. Grieco's answer to yield combinations. This should give all possible answers. — pylang
– pylang, Commented Dec 2, 2016 at 15:06

infotoni91 · Accepted Answer · 2016-12-05 07:15:34Z

2

This is indeed a very complex task. This solution only provides a basic approach. It's poor and unreviewed in e.g. terms of performance.

import itertools

load_data = [1, 2, 3, 4, 10, 20]
maximum = 35

def selection(data, maximum):
    for count in range(1,len(data)+1):
        for combination in itertools.combinations(data, count):
            if maximum == sum(combination):
                yield combination

i = list(selection(load_data, maximum))
print (i)

And please, avoid using global variables. This is very bad style.

edited Dec 5, 2016 at 7:15

answered Dec 2, 2016 at 12:55

infotoni91

7213 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Skycc Over a year ago

Can use itertools.combinations instead of permutations, it reduce repeated values

pylang Over a year ago

If instead you yield combination, you can get a list of all combinations whose sums equal maximum, e.g. list(selection(load_data, 35)) --> [(1, 4, 10, 20), (2, 3, 10, 20)]. I think this will generalize your answer.

pylang Over a year ago

Btw consider including the list comprehension version of your code:

[c for count in range(1,len(load_data)+1)     for c in itertools.combinations(load_data, count)      if maximum == sum(c)]

Marek Nowaczyk · Accepted Answer · 2016-12-02 14:29:51Z

2

Here you are:

load_data = [1, 2, 3, 4, 10, 20]
global value 
value = 30

def process(m): 
    print m

def selection():
    # make a local copy of load_data
    data = load_data[:]
    global value  # <- value is the input 
    while data and (value > 0):
        maxval = max(data)
        posix = data.index(maxval)
        if posix >=0:
            value = value - data[posix] # <- subtract max value from input and repeat process 
            process(data[posix])
            data.pop(posix)  
selection()

, but as A. Grieco said, it's very simple and basic aproach to problem.

If load_data list is constant, and always has elements from example, then you should just sort descending the load_data first, so the bigger elements are processing first, for optimization purposes.

I.e:

load_data = [1, 2, 3, 4, 10, 20]
global value 
value = 30

def process(m): 
    print m

def selection():
    # make a local copy of load_data
    data = sorted(load_data[:],reverse=True)
    global value  # <- value is the input 
    for v in data:
        if value -v >= 0:        
            value -= v 
            process(v)
        if value -v == 0:
            break

selection()

edited Dec 2, 2016 at 14:29

answered Dec 2, 2016 at 12:58

Marek Nowaczyk

2571 silver badge5 bronze badges

3 Comments

Skycc Over a year ago

can just use data = sorted(load_data, reverse=True) instead of the comparer function

Marek Nowaczyk Over a year ago

Thanks Skycc. Code is improved now.

pylang Over a year ago

Concise example. Is there a reason to use global? Why not use a function parameter pass in value e.g. def selection(value): ... then call selection(30).

Collectives™ on Stack Overflow

Selecting max elements from list using input value Python

2 Answers 2

3 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related