omn*_*sis 8 algorithm optimization knapsack-problem dynamic-programming
我有一个问题,表面看起来像0-1背包.我有一组可以选择(或不选择)的可能"候选人",每个候选人都有"权重"(成本)和潜在的"价值".如果这是整个问题,我会使用DP方法并完成它.但是这里是曲线球:对最终解决方案中可能的候选者存在"分区约束".
我的意思是候选空间被分成不连续的等价类.对于我的特殊问题,大约有300个候选人和12个可能的等同类.有"商务规则"说我只能说C1级的3名候选人和C2级的6名候选人.
这种约束建议使用分支定界技术或其他形式的修剪的图搜索类型方法,但是由于我只熟悉0-1背包的DP解决方案,我有点难以理解.哪些技术/方法可能适合这个问题？我也想过可能使用约束编程库但不确定它是否能够找到解决方案？
您可以尝试整数线性规划求解器，其中有一个用于选择每个候选者的二进制变量。约束很容易表达为线性不等式。对于 300 个变量，求解器求解应该不会有太大困难。
最简单的方法可能是以文本格式（例如CPLEX LP 格式）编写问题，然后使用 Coin CBC 或 GLPK 等求解器。