0-1背包问题中加入分区限制

Question

8

我有一个问题，看起来像是0-1背包问题。我有一组可能的“候选项”可供选择（或不选），每个候选项都有一个“权重”（成本）和潜在的“价值”。如果仅仅是这个问题，我会采用DP方法并解决它。但是这里有一个曲线球：可能的候选项被“分区约束”所限制，这些候选项可以出现在最终的解决方案中。

我的意思是，候选空间被分成了离散的等价类。对于我的问题，大约有300个候选项和12个可能的等价类。有“商业规则”规定，我只能从C1类中选择最多3个候选人，从C2类中选择最多6个候选人，等等。

这种约束建议使用图搜索类型的方法，使用分支和限界技术或其他形式的修剪。然而，我有点困惑如何开始，因为我只熟悉0-1背包问题的DP解决方案。哪些技术/方法可能适用于这个问题？我也考虑过使用约束编程库，但不确定它是否能够找到解决方案？

- omnisis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Falk Hüffner · Accepted Answer

你可以尝试使用整数线性规划求解器，其中每个候选人都有一个二进制变量可供选择。约束条件可以很容易地表示为线性不等式。对于300个变量，求解器应该没有太大的问题。

最简单的方法可能是将问题以文本格式编写，例如CPLEX LP format，然后使用Coin CBC或GLPK等求解器。