從字典中選擇最佳組選擇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結束。