python - 从字典 Python 中选择最佳组

Question

所以我有一个带有 key:value(tuple) 的字典。像这样的东西。 {"名称":(4,5),....} 其中(4,5)代表两个类别(cat1, cat2)。给定第二类的最大数量，我想找到字典条目的最佳组合，以使第一类最大化或最小化。

例如，如果 maxCat2 = 15，我想从字典中找到一些条目组合，当我将每个条目的 cat2 值加在一起时，我小于 15。可能有很多这样的条件。在这些可能性中，我想选择一种，当我为每个条目添加 cat1 的值时，它大于任何其他可能性。

我考虑编写一种算法来获取字典中条目的所有排列，然后查看每个条目是否满足 maxCat2 标准，然后查看其中哪一个给我最大的总 cat1 值。如果我有 20 个条目，那就意味着我会检查 20 个!组合，这是一个非常大的数字。我可以做些什么来避免这种情况吗？谢谢。

Answer 1

作为Jochen Ritzel指出，这可以看作是 knapsack problem 的一个实例.

通常，您有一组同时具有“重量”(在您的示例中为“第二类”)和“值(value)”(或“成本”，如果是最小化问题)的对象。

问题在于选择对象的一个​​子集，使其“值”的总和最大化/最小化，受制于权重总和不能超过指定最大值的约束。

虽然这个问题在一般情况下是棘手的，但如果对权重和的最大值的约束是固定的，则存在使用 dynamic programming 的多项式时间解。或 memoization .

从广义上讲，这个想法是定义一组值，其中

C_ij 表示仅考虑前 i 个对象的最大总和(“值”)，其中总重量(的选择的子集)不能超过 j。

这里有两种可能的选择来计算C_ij。

• 任一元素 i 包含在子集中，然后

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

• 或元素 i 不在所选对象的子集中，所以

  C_ij = C_i-1,j

需要取两者中的最大值。

如果n是元素个数，w是最大总权重，那么答案就在C_nw .