確定最佳組合的算法 - 裝箱包裝

Question

給定一組項目，每個項目都有一個值，確定要包含在一個集合中的每個項目的數量，以使總值小於或等於給定限制，並且總值儘可能大。

實施例：

 
Product A = 4 
Product B = 3 
Product C = 2 
Product D = 5 

If Total Capacity = 10.5 , then the combination of B,C,D will be selected. 
If Total Capacity = 12.5 , then the combination of A,B,D will be selected. 
If Total Capacity = 17 , then the combination of A,B,C,D will be selected. 

我尋找一種算法（如揹包或裝箱）來確定組合。任何幫助讚賞。

Answer 1

你說這是「像揹包」。據我所知，這是bounded knapsack problem稱爲0-1揹包問題的特殊情況。

它是NP完整的。

有很多方法可以嘗試解決它。請參閱此相關的問題的一種方法：

• Writing Simulated Annealing algorithm for 0-1 knapsack in C#

如果你只有四個項目則只是測試的所有可能性應該是最大的目的不夠快。