0

Summary: I have around 50 variables, which all have a value. And I would like to get all possible combinations of variables with a maximum value.

For example: I have variables 'grape: € 0,1', 'apple: € 1', 'banana: € 2,5', 'strawberry: € 4', 'orange: € 5' etc. And I want to get all possible combinations that one can make when having € 5. Also, each variable can be picked once (for example not 5 x apple) and there is a maximum to the number of variables that can be picked.

Above example is a simplification of my problem.

Background: I have not tried anything yet. I think I have to read in my variables as a dictionary. But for the rest I do not have a clue how to solve this problem in Python.

Code: Not (yet) available

Expected output: The output should be all possible combinations of variables that match the condition of containing maximum 'x' variables and represent maximum 'x' value and that each variable is picked not more than once.

Tom
  • 1
  • 2
  • 2
    You know that this optimization problem is NP-hard and not so easy to calculate ;-) The problem itself is very famous and you can find it on Wikipedia etc. – Tobias S Aug 22 '19 at 12:14
  • Unfortunately we cannot simply generate the code for you, Stack Overflow is not a code writing service. However, a couple of Google searches would yield things like https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum to give you a starting place. – artemis Aug 22 '19 at 12:18
  • I was not aware that this is such a well known and complex question. I thought there would be some kind of function (itertools.combinations seems useful indeed) to settle this. But thank you for your recommendations, Tobias, Jerry and Grzegorz! – Tom Aug 22 '19 at 14:46

2 Answers2

0

Try this one to start with:

import itertools

x=[0.1, 1, 2.5, 4, 5]
N = 5
res = []
for i in range(len(x)):
    for el in itertools.combinations(x, i+1):
        if(sum(el)<=N and N-sum(el) < min([el_sub for el_sub in x if el_sub not in el] or [N])):
            res.append(el)
            print(el)

Result you will find in "res". If you want to restrict number of elements - play with the first for loop (and if statement accordingly).

Grzegorz Skibinski
  • 12,624
  • 2
  • 11
  • 34
0

I have also found a technical solution myself. But it takes a lot of processing power, to much I would say. In my case there were 48 variables and I wanted all possible combinations with 20 of them. I believe there are around 9.000.000.000 possible combinations. So Python could not handle this properly. Anyway, my code is below (for 26 fruits and all combinations of 12 of them):

from itertools import combinations

fruits = [
{'A':1.5},
{'B':1.5},
{'C':0.75},
{'D':1.5},
{'E':2.5},
{'F':3.5},
{'G':1},
{'H':0.5},
{'I':2.5},
{'J':1},
{'K':0.75},
{'L':3},
{'M':0.5},
{'N':0.75},
{'O':1},
{'P':1},
{'Q':1.5},
{'R':2},
{'S':3.5},
{'T':3},
{'U':0.75},
{'V':2},
{'W':2},
{'X':1.5},
{'Y':4},
{'Z':1.5}
]

combis = list(combinations(fruits,12))

for combi in combis:
    total = 0
    for fruit in combi:
        fruit = fruit.values()
        string = (list(value))
        integer = (string[0])
        total = total + integer
    if total == 23.5:
        print(list(combi[0].keys())[0]), print(list(combi[1].keys())[0]), print(list(combi[2].keys())[0]), 
        print(list(combi[3].keys())[0]), print(list(combi[4].keys())[0]), print(list(combi[5].keys())[0]),
        print(list(combi[6].keys())[0]), print(list(combi[7].keys())[0]), print(list(combi[8].keys())[0]), 
        print(list(combi[9].keys())[0]), print(list(combi[10].keys())[0]), print(list(combi[11].keys())[0]), 
        print(som), print('_______________')
    else:
        pass
Tom
  • 1
  • 2