所以我有一个带key:value（元组）的字典。像这样的东西。{“name”：（4,5），…}其中
（4,5）表示两类（类别1、类别2）给定第二类的最大数目，我想找到字典条目的最佳组合，使得第一类被最大化或最小化。
例如，如果maxcat2=15，我想从字典中找到一些条目的组合，这样，当我将每个条目的cat2值相加时，我就不到15。可能有很多这样的情况。在这些可能性中，我想选择一个，当我为每个条目加上cat1的值时，它比任何其他可能性都大。
我考虑编写一个算法来获取字典中所有条目的排列，然后看看每个条目是否满足maxcat2标准，然后看看哪个条目的总cat1值最大。如果我有20个条目，那意味着我会检查20个！组合，这是一个非常大的数字有什么我可以避免的吗？谢谢。
最佳答案
正如Jochen Ritzel所指出的，这可以看作knapsack problem的一个实例。
通常，您有一组既有“权重”（在您的示例中是“第二类”）又有“值”（如果是最小化问题，则为“成本”）的对象。
问题在于选择对象的子集，使得它们的“值”的总和最大化/最小化，受约束的权重总和不能超过指定的最大值。
虽然这个问题一般是难以解决的，但是如果对权重之和的最大值的约束是固定的，则存在一个使用dynamic programming或memoization的多项式时间解。
广义上讲，我们的想法是定义一组值，其中
CIJ表示可获得的最大值和（值），仅考虑第一个I对象，其中所选择的子集的总重量不能超过J。
这里有两种可能的选择来计算cij。
其中一个元素i包含在子集中，然后
Ci j=值i+Ci-1，j-权重i
或者元素i不在所选对象的子集中，所以
ci j=ci-1，j
两者的最大值需要选择。
如果n是元素的数量，w是最大总重量，那么答案以CNW结尾。
关于python - 从字典Python中选择最佳群组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5746689/