0-1 带有分区约束的背包
我有一个问题，表面上看起来像 0-1 背包。我有一组可能的“候选者”可以选择（或不选择），每个候选者都有一个“权重”（成本）和一个潜在的“价值”。如果这就是整个问题，我会使用 DP 方法并解决它。但问题是：最终解决方案中可能存在的候选者存在“分区约束”。
我的意思是候选空间被分成离散的等价类。对于我的特定问题，大约有 300 个候选者和 12 个可能的等价类。有“业务规则”规定我最多只能有 3 个来自 C1 类的候选者和来自 C2 类的 6 个候选者，等等。
此约束建议使用分支定界技术或某种其他形式的修剪的图搜索类型方法，但是我对如何开始有些困惑，因为我只熟悉 0-1 Knapsack 的 DP 解决方案。哪些技术/方法可能适合解决这个问题？我也想过也许使用约束编程库，但不确定它是否能够找到解决方案？
I have a problem that on the surface looks like 0-1 knapsack. I have a set of possible "candidates" that can be choosen (or not), each candidate has a "weight" (cost) and a potential "value". Were this the entire problem, I'd use a DP approach and be done with it. But here's the curveball: There are "partitioning constraints" on the possible candidates that can be in the final solution.
What I mean is that the candidate space is split into discrete equivalence classes. For my particular problem there are about 300 candidates and 12 possible equivalence classes. There are "buisness rules" that say I can only have up to say 3 candidates from class C1 and 6 candidates from C2, etc.
This constraint suggests a graph-search type approach using branch-and-bound techniques or some other form of pruning, however I am somewhat stumped as to how to began since I am only familiar with the DP solution to 0-1 Knapsack. What techniques/approaches might be suitable for this problem? I also thought of maybe using a constraint programming library but am not sure if it would be able to find a solution?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以尝试整数线性规划求解器，其中有一个用于选择每个候选者的二进制变量。约束很容易表达为线性不等式。对于 300 个变量，求解器求解应该不会有太大困难。
最简单的方法可能是以文本格式编写您的问题，例如 CPLEX LP 格式< /a>，然后使用 Coin CBC 或 GLPK 等求解器。
You could try an Integer Linear Programming solver, where there is a binary variable for choosing each candidate. The constraints are easily expressed as linear inequations. With 300 variables, a solver should not have much trouble solving it.
The easiest way would probably be to write your problem in a text format such as the CPLEX LP format, and then use a solver like Coin CBC or GLPK.