查找整數數組中給定數值的最小集合

Question

給定總和s和一個正整數數組，找到元素總和爲s的最小子集。例如，給定數組{1,2,3,4,5}並且和s = 8，最小子集將是{3,5}。

到目前爲止，我可以解決的a一組整數，使用遞歸加起來的貪婪方法，但我找不到如何找到最小子集。我應該研究一個特定的算法嗎？

Answer 1

這是「零一平等揹包問題」。這是NP完整的。然而，存在多種有效的算法。

1. 如果總和小到足以分配的存儲器，許多位和在它們之間迭代N（數組元素的數）倍時，可以使用dynamic programming.

2. Mixed-integer program解算器等CPLEX，Gurobi，和SCIP通常會在實踐中可能出現的「典型」情況下做得相當好。在將揹包問題作爲MIP解算器的輸入時，需要注意一些問題以避免精確性問題。

3. 如果你能容忍一些不精確：Polynomial-time approximation schemes爲不平等揹包（您想最小的一組數字，在將多數總結的東西）的存在，是不是太難形容：規模涉及的所有號碼直到您可以執行動態編程並處理結果。如果您注意接受近似問題的近似解，也可以使用相同的方法獲得近似解揹包揹包。