对于一个背包,动态规划算法可以有效地实现最优填充。但是是否有已知的高效算法可以最优地填充两个背包(容量可以不同)?
我尝试了以下两种方法,但都不正确。
- 使用原始DP算法填充一个背包,然后再填充另一个背包。
- 首先填充大小为“W1 + W2”的背包,然后将解决方案分成两个解决方案(其中W1和W2是两个背包的容量)。
问题陈述(也可以在维基百科上查看背包问题):
我们必须用一组物品(每个物品具有重量和价值)填满背包,以便在总重量小于或等于背包大小的情况下最大化从物品中获得的价值。
我们不能多次使用一个物品。
- 我们不能使用部分物品。我们不能取物品的一部分。(每个物品必须完全包括或不包括)。