Complex 0/1 背包，带多个隔层
Complex 0/1 Backpack with multiple compartments
假设我的背包里有 3 个隔层：红色、绿色、蓝色和 3 组物品：红色物品、绿色物品和蓝色物品，它们都有重量和好处。我还要求背包的每个隔间必须放置的物品总数。红色隔间必须有 2 个红色物品，绿色隔间必须有 3 个绿色物品，蓝色隔间必须有 3 个蓝色物品。我的背包可以承受某种最大重量。我需要在给定一些权重的情况下针对最大值进行优化。
为了解决这个问题，我尝试使用用于解决 0/1 backback 的分支定界技术。这种技术计算速度很快，但会选择剩余 space 太多的项目，而不是 return 最佳项目。
可以使用哪些技术在合理的时间内解决这个问题（也就是不强制使用所有可能的组合）？我不熟悉动态规划，但这是更适合动态规划的东西还是我可以使用其他技术？
很有意思的问题！是的，这个问题可以用动态规划来解决。
要了解如何求解，首先需要了解如何使用动态规划求解背包：http://en.wikipedia.org/wiki/Knapsack_problem。
可以看到递归函数求解Knapsack只有一个参数，就是剩余重量。要修改您的问题，您需要 "drag" 以及另外三个参数，这些参数存储我们与满足每个隔间条件的接近程度。因此，递归函数将有 4 个参数。
希望对您有所帮助。
假设我的背包里有 3 个隔层：红色、绿色、蓝色和 3 组物品：红色物品、绿色物品和蓝色物品，它们都有重量和好处。我还要求背包的每个隔间必须放置的物品总数。红色隔间必须有 2 个红色物品，绿色隔间必须有 3 个绿色物品，蓝色隔间必须有 3 个蓝色物品。我的背包可以承受某种最大重量。我需要在给定一些权重的情况下针对最大值进行优化。
为了解决这个问题，我尝试使用用于解决 0/1 backback 的分支定界技术。这种技术计算速度很快，但会选择剩余 space 太多的项目，而不是 return 最佳项目。
可以使用哪些技术在合理的时间内解决这个问题（也就是不强制使用所有可能的组合）？我不熟悉动态规划，但这是更适合动态规划的东西还是我可以使用其他技术？
很有意思的问题！是的，这个问题可以用动态规划来解决。
要了解如何求解，首先需要了解如何使用动态规划求解背包：http://en.wikipedia.org/wiki/Knapsack_problem。
可以看到递归函数求解Knapsack只有一个参数，就是剩余重量。要修改您的问题，您需要 "drag" 以及另外三个参数，这些参数存储我们与满足每个隔间条件的接近程度。因此，递归函数将有 4 个参数。
希望对您有所帮助。