复式0/1多隔间背包

Question

假设我的背包里有三个车厢:红色、绿色、蓝色和3套物品:红色物品、绿色物品和蓝色物品，它们都有重量和效益。我也有一个要求，大约总项目的总数量，必须放在每个车厢的背包。红色隔间必须有2个红色物品，绿色隔间必须有3个绿色物品，蓝色隔间必须有3个蓝色物品。我的背包能承受某种最大重量。我需要优化给出一些权重的最大值。

为了解决这个问题，我尝试使用用于解决0/1回溯的分支和绑定技术。这种技术计算速度快，但选择的项目留下太多的空间，而不返回最优的项目。

有什么技术可以在合理的时间内解决这个问题(也不是蛮横的强迫每一个可能的组合)？我不熟悉动态编程，但这是更适合这种情况的东西还是我可以使用的另一种技术？

Answer 1

非常有趣的问题！是的，这个问题可以用动态规划来解决。

要理解如何解决问题，首先需要了解如何使用动态编程：problem解决背包问题。

您可以看到递归函数求解背包只有一个参数，即剩余权重。要修改您的问题，您需要“拖动”另外三个参数，这些参数存储的距离非常接近于满足每个舱室的条件。因此，递归函数将有4个参数。

希望这能有所帮助。