Optimal group selection from a dictionary Python

So I have a dictionary with key:value(tuple). Something like this. {"name":(4,5),....} where (4,5) represents two categories (cat1, cat2). Given a maximum number for the second category, I would like to find the optimal combination of dictionary entries such that the 1st category is maximized or minimized.

For example, if maxCat2 = 15, I want to find some combinati开发者_开发技巧on of entries from the dictionary such that, when I add the cat2 values from each entry together, I'm under 15. There may be many such conditions. Of these possibilities, I would like to pick the one that when I add up the values for cat1 for each entry it is larger than any of the other possibilities.

I thought about writing an algorithm to get all permutations of the entries in the dictionary and then see if each one meets the maxCat2 criteria and then see which one of those gives me the largest total cat1 value. If I have 20 entries, that means I would check 20! combinations, which is a very large number. Is there anything that I can do to avoid this? Thanks.

As Jochen Ritzel pointed out, this can be seen as an instance of the knapsack problem.

Typically, you have a set of objects that have both "weight" (the "second category", in your example) and "value" (or "cost", if it is a minimization problem).

The problem consists in picking a subset of the objects such that the sum of their "values" is maximized/minimized, subject to the constraint the sum of the weights cannot exceed a specified maximum.

Though the problem is intractable in general, if the constraint on the maximum value for the sum of weights is fixed, there exists a polynomial time solution using dynamic programming or memoization.

Very broadly, the idea is to define a set of values where

C_ij denotes the maximum sum (of "values") attainable considering only the first i objects where the total weight (of the chosen subset) cannot exceed j.

There are two possible choices here to calculate C_ij .

• either element i is included in the subset and then

  C_ij = value_i + C_{i-1,j-weighti}

• or element i is not in the subset of chosen objects, so

  C_ij = C_i-1,j

The maximum of the two needs to be picked.

If n is the number of elements and w is the maximum total weight, then the answer ends up in C_nw.