Subset sum problem using key value pairs

I have an algorithm that outputs a subset which sums up to a value as close to integer s as possible

from itertools import combinations

products = {
    "Apple": 5,
    "Pear": 4,
    "Banana": 8,
    "Strawberry": 7,
    "Watermelon": 9,
    "Lemon": 6,
}


def closest_subset(s, nums):
    return min((
        c
        for i in range(1, len(nums)   1)
        for c in combinations(nums, i)
    ), key=lambda x: abs(s - sum(x)))


print(closest_subset(11, products.values()))

# Output: (5, 6)

Instead, I would like to output items from the dictionary, like this:

# Desired output
{
    "Apple": 5,
    "Lemon": 6,
}

How can I modify my code to achieve this?

CodePudding user response：

You can modify it, by passing the dictionary items instead of the values to the function. To clarify this, I have replaced nums in the code with items. The rest of the function works basically the same way, but the combinations give you combinations of tuples containing the key and the value. Therefore, you have to slightly adjust your min function key, so that it only takes into account the second value v2of each tuple, which is the actual amount. Then, the min function returns a tuple pof tuples of key and value pairs, which you can then convert to a dictionary before returning.

from itertools import combinations

products = {
    "Apple": 5,
    "Pear": 4,
    "Banana": 8,
    "Strawberry": 7,
    "Watermelon": 9,
    "Lemon": 6,
}


def closest_subset(s, items):
    return dict(min((
        c
        for i in range(1, len(items)   1)
        for c in combinations(items, i)
    ), key=lambda x: abs(s - sum([v2 for v1, v2 in x]))))


print(closest_subset(11, products.items()))

# Output: {'Apple': 5, 'Lemon': 6}