我正在嘗試解決以下問題，但不確定我應該使用哪種算法。它在大規模鑑定領域。對片段提議算法的建議
我有一系列的「權重」，* w_i *，它可以總和達到總重量。測得的總重量有一個與之相關的誤差，因此是不準確的。
我需要找到，給定的總重量Ť，可以總結爲總，其中ķ是來自用戶的輸入權重的最接近ķ可能的組合。每個重量可以使用多次。現在
，這聽起來很像有界整數倍揹包問題，但是
我可以解決它使用揹包問題的多個sweeps，從weight-error-> weight + error，通過步入小足夠的增量，但是如果增量太大而不能丟失可以使用的某些重量組合，則可能會增加。
權重的數目通常很小（4 - > 10點的權重）和總重量與平均重量的比值通常約爲2或3
沒有人知道的算法可能是名稱適合在這裏？
你的問題有效地類似於NP完全問題的揹包問題。
對於真正有限數量的權重，您可以運行每個組合的重複，然後進行排序，從而爲您提供相當高的操作數量;最好：組合爲(n + k - 1)!/((n - 1)! · k!)，排序部分爲n·log(n)。
在合理的時間內解決這類問題最好是通過現在的演化算法來完成。
如果採取從DEAP下面的例子中，在Python進化算法框架： ga_knapsack.py，你認識到通過修改線58-59自動丟棄的東西平滑超重溶液（具有線性關係，例如），它會在比蠻力更短的時間內爲您提供接近最佳解決方案的解決方案。按照您的要求，解決方案已經在最後爲您排序。
它是一個好主意，但缺少可能的解決方案是一個問題。我曾希望對揹包算法進行某種形式的回溯修改，我可以解決一個超重揹包問題，然後遍歷所有可能的權重組合。 – AlgQuery
NP完全問題指定如果不探索整個解決方案空間，可能會錯過解決方案。如果你總是需要最佳的解決方案，那麼強制是強制性的。這個答案提出了一個蠻力算法。 – Soravux
我的印象是，您仍然可以使用動態編程方法，以NP完整問題有效挑選出發點。我不確定這樣的遍歷是否可能 - 解決方案空間可能是「顛簸」並且很難預測 - 我想，如果我要使用揹包方法（正如我在原始問題中所述），那麼問題是解決方案空間遍歷 - 如果這樣的事情是可能的。 – AlgQuery
作爲第一次嘗試我會去約束編程（但當時我幾乎總是這樣，所以採取建議用少許鹽）：
我只是意識到，你還希望參數化op \ elem +， - （權重和誤差項的任意組合）表達式w_n op e_m，並且關閉我的頭頂部，我不知道哪個約束求解器可以讓你做到這一點。無論如何，你總是可以回到序言。它可能不會飛，特別是如果你有很多的重量，但它會迅速給你解決方案。
如果只有4-10重量，你可以蠻力。 – Dukeling
速度是一個問題，因爲不同的輸入需要重複解決問題。此外，總重量與最小重量比可以相當高<200 – AlgQuery
有多少關注？我估計蠻力10或更少的元素應該不到一秒鐘。 – Dukeling