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

Question

所以我有一个关键字：值（元组）的字典。像这样的东西。 {“name”:(4,5），....}其中 （4,5）代表两个类别（cat1，cat2）。给定第二个类别的最大数量，我想找到字典条目的最佳组合，使第一个类别最大化或最小化。

例如，如果maxCat2 = 15，我想从词典中找到一些条目的组合，这样当我将每个条目的cat2值加在一起时，我就不到15条了。可能有很多这样的条件。在这些可能性中，我想挑选一个当我为每个条目加上cat1的值时，它比任何其他可能性都大的那个。

我想过要编写一个算法来获取字典中条目的所有排列，然后查看每个条目是否符合maxCat2条件，然后查看哪些条目给了我最大的总cat1值。如果我有20个参赛作品，这意味着我会检查20！组合，这是一个非常大的数字。有什么我可以做，以避免这种情况？谢谢。

Answer 1

由于Jochen Ritzel指出，这可以看作是knapsack problem的一个实例。

通常，您有一组既有“重量”（在您的示例中为“第二类”）和“价值”（或“成本”，如果是最小化问题）的对象。

问题在于挑选对象的一个​​子集，使得它们的“值”的总和被最大化/最小化，受限于权重的总和不能超过指定的最大值。

虽然问题一般难以解决，但如果对权重总和的最大值的约束是固定的，则存在使用dynamic programming或memoization的多项式时间解决方案。

非常广泛地说，思想是定义的一组值，其中

Ç _IJ表示最大总和（的“值”）可达到仅考虑第一我对象，其中总重量（选择的子集）不能超过j。

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

• 任一元素我被包括在子集，然后

  Ç _IJ = 值_我 + Ç _{I-1，J-重量我}

• 或元件我不是选择对象的子集，因此

  Ç _IJ = Ç _I-1，J

两者的最大值需要pi cked。

如果Ñ是元素瓦特的数目，为最大的总重量，那么答案在Ç _NW结束。