使用键值对的子集求和问题 - python

Question

我有一个算法可以输出一个子集，该子集的总和值尽可能接近整数 s

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)

相反，我想从字典中输出项目，如下所示：

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

如何修改我的代码来实现此目的？

Answer 1

您可以修改它，将字典项而不是值传递给函数。为了澄清这一点，我将代码中的 nums 替换为 items。该函数的其余部分基本上以相同的方式工作，但组合为您提供了包含键和值的元组组合。因此，您必须稍微调整您的 min 函数 key，使其仅考虑每个元组的第二个值 v2，即实际金额。然后，min 函数 returns 元组 pof 键和值对的元组，然后您可以在返回之前将其转换为字典。

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}

使用键值对的子集求和问题 - python

Subset sum problem using key value pairs - python

python

algorithm

key-value

itertools

subset-sum