揹包問題的變體

Question

我有'n'數量（非負整數）。我的要求是確定一個最佳的金額組合，以便組合的總和小於或等於給定的固定限制，並且總數儘可能大。可以包含在最佳集合中的數量沒有限制。

例如起見：量143,2054,546,3564,1402和給定的極限是5000。

按我理解揹包問題具有用於每個項目（重量和價值）2點的屬性。但上述問題只有一個屬性（數量）。我希望這會讓事情變得更簡單？ :)

有人可以幫助我解決這個問題的算法或源代碼？

Answer 1

這仍是一個NP難問題，但如果你想（或必須）做類似的東西，也許這個主題幫助您了一點：

find two or more numbers from a list of numbers that add up towards a given amount

其中i solved it like this並NikiC修改它to be faster。唯一的不同之處在於：一個是獲取準確金額，而不是「儘可能接近」，但這只是代碼中的一些小改動（並且必須將其翻譯成您正在使用的語言）。

看看我的代碼中的註釋，以瞭解我試圖做的，至極，總之形式：

• 計算給定部分的所有可能的組合，總結起來
• 如果結果是我要找的量，該解決方案保存到一個數組
• 至少，排序的所有可能的解決方案，以獲得一個使用至少部分

所以你必須改變：

• 節省的解決方案，如果它不是你要找的總量，而不是使用的零件

Answer 2

本書"Knapsack Problems"數

排序方案由Hans Kellerer，烏爾裏希Pferschy和量低David Pisinger稱之爲子集總和問題，並將整章（第4章）專用於它。本章非常全面，涵蓋了算法和計算結果。

即使這個問題是揹包問題的一個特例，它仍然是NP難題。