分集合选元素的双约束利润最大化优化问题名称及归类问询
问题描述
我遇到一个组合优化问题,不清楚其学术领域中的名称。具体问题如下:
- 存在n个包含互斥元素的集合,每个元素仅属于一个集合
- 每个元素具有2个约束值和1个利润值
- 需要从每个集合中选择一个元素,在确保各约束值总和不超过指定上限的前提下,最大化利润总和
请问该问题是否为已被研究的问题?其名称是什么?能否归为某类已研究问题?
问题解答
感谢@Berthur和@mrBen的解答,该问题属于带集合选择约束的多约束背包问题(multiple-constrained knapsack problem),核心是需要引入指示变量来强制实现「每个集合仅选一个元素」的约束,本质上是多约束背包问题的变种,属于已被广泛研究的组合优化问题范畴。
内容的提问来源于stack exchange,提问作者Max
相关产品推荐
相关产品推荐

