我有一个问题,看起来像是0-1背包问题。我有一组可能的“候选项”可供选择(或不选),每个候选项都有一个“权重”(成本)和潜在的“价值”。如果仅仅是这个问题,我会采用DP方法并解决它。但是这里有一个曲线球:可能的候选项被“分区约束”所限制,这些候选项可以出现在最终的解决方案中。
我的意思是,候选空间被分成了离散的等价类。对于我的问题,大约有300个候选项和12个可能的等价类。有“商业规则”规定,我只能从C1类中选择最多3个候选人,从C2类中选择最多6个候选人,等等。
这种约束建议使用图搜索类型的方法,使用分支和限界技术或其他形式的修剪。然而,我有点困惑如何开始,因为我只熟悉0-1背包问题的DP解决方案。哪些技术/方法可能适用于这个问题?我也考虑过使用约束编程库,但不确定它是否能够找到解决方案?
我的意思是,候选空间被分成了离散的等价类。对于我的问题,大约有300个候选项和12个可能的等价类。有“商业规则”规定,我只能从C1类中选择最多3个候选人,从C2类中选择最多6个候选人,等等。
这种约束建议使用图搜索类型的方法,使用分支和限界技术或其他形式的修剪。然而,我有点困惑如何开始,因为我只熟悉0-1背包问题的DP解决方案。哪些技术/方法可能适用于这个问题?我也考虑过使用约束编程库,但不确定它是否能够找到解决方案?