複雜0/1揹包有多個隔層

Question

說我揹包裏有3個隔間：紅色，綠色，藍色和3套物品：紅色物品，綠色物品和藍色物品，都有重量和好處。我還要求在揹包的每個隔間中必須放置的總物品總數。紅色隔間必須有2個紅色物品，綠色隔間必須有3個綠色物品，藍色隔間必須有3個藍色物品。我的揹包可以承受某種最大重量。我需要針對給定重量的最大值進行優化。

爲了解決這個問題，我試圖使用分支和綁定技術來解決0/1回退。這種技術可以快速計算，但挑選的物品會留下太多空間，並且不會返回最佳物品。

什麼技術可以用來在合理的時間內解決這個問題（又不是強制每種可能的組合）？我對動態編程不熟悉，但是這更適合於這個，或者我可以使用其他技術嗎？

Answer 1

非常有趣的問題！是的，這個問題可以通過動態編程來解決。

要理解如何解決，首先需要了解如何使用動態編程來解決揹包問題：http://en.wikipedia.org/wiki/Knapsack_problem。

您可以看到，解決Knapsack的遞歸函數只有一個參數，即剩餘權重。爲了修改你的問題，你需要沿着另外三個參數「拖動」，這個參數存儲瞭如何接近實現我們每個艙室的條件。遞歸函數因此會有4個參數。

希望這會有所幫助。