Combinations meeting criteria in Python

StackOverflow https://stackoverflow.com/questions/21081438

Question

I have a dict of names and numbers ranging from 700 to 2500, and I want to combine them in a new list where the sum of the group don't go over 4500. Then I'll pick the one with least amount of entries.

I know I can make a list of all possible combinations then delete the entries that goes past the 4500, but that would make far too many unusable items.

Any hint?

Update: Thanks to @Andrea de Marco I have part of the problem.

With the knapsack function now I have the best entry, but not all entries are in the list. So I have to run the function n times until the list is empty.

Since I'm not using any 'value' for the problem I set the value to 1.

OTHER TIPS

If you want to play with different combinations of items, you want itertools. This will allow you to generate all the possible combinations of items without actually filling your memory by building the whole lot at once. You will probably find this recipe useful:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

You can use this to generate all the combinations of the values() in your dictionary.

Assuming that you want to get as close as possible to some target but with as few values as possible, you could try:

best = None
for set_ in powerset(d.values()):
    if best is None and sum(set_) <= target:
        best = set_
    elif (sum(best) < sum(set_) <= target or # closer or
          (sum(best) == sum(set_) and # as close and 
           len(set_) < len(best))): # shorter
        best = set_

However, note that this naïve brute force approach is incredibly slow as len(d.values()) gets larger; the number of subsets in the powerset of set S is 2**n, where n == len(S).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top