求将对象最优划分为给定带权分组、获取最大总权重的高效算法

你描述的问题是组合优化领域的经典问题：加权集合装填问题（Weighted Set Packing Problem），核心要求就是从给定的带权集合中选出互不相交的子集，最大化选中集合的总权重，和你的需求完全匹配。

不同规模下的高效解决方案 #

你之前提到的全遍历方案时间复杂度为O(2^M)（M为分组总数），规模稍大就不可行，根据数据量级可以选择以下更高效的方案：

小数据量级（对象总数≤20）：二进制动态规划 #

用二进制掩码表示已被占用的对象，复杂度远低于全遍历：

• 给每个对象分配唯一的二进制位，每个分组也可以转换为对应的掩码g_mask（分组包含的对象对应位设为1）
• 定义dp[mask]为对象占用状态为mask时可获得的最大权重，初始值dp[0]=0，其余状态初始为负无穷
• 遍历所有状态mask，再遍历所有未被排除的分组：如果分组的g_mask和当前mask没有重叠（即mask & g_mask == 0），则可以更新新状态dp[mask | g_mask] = max(dp[mask | g_mask], dp[mask] + 分组权重)
• 最终所有dp[mask]中的最大值就是最优解
  该方案时间复杂度为O(M*2^N)，N为对象总数，只要N≤20就可以快速得到精确最优解。

中等数据量级（对象数≤1000，分组数≤10000）：整数线性规划求解 #

你可以直接用成熟的整数线性规划（ILP）求解器计算精确最优解，建模逻辑非常简单：

• 定义变量x_i为0/1变量，1代表选中第i个分组，0代表不选
• 目标函数：最大化sum(x_i * w_i)，w_i为第i个分组的权重
• 约束条件：对每个对象，所有包含该对象的分组对应的x_i之和≤1，保证对象不会重复分配
  目前开源的CBC、商用的Gurobi等求解器都内置了分支定界、剪枝等优化，大部分工业级实际数据集都可以快速算出精确结果。

大数据量级/对性能要求极高：贪心近似解 #

如果不要求100%精确的最优解，只需要快速得到接近最优的结果，可以用贪心策略：

• 每次选择「单位对象权重最高」的分组（即分组权重除以分组包含的对象数量）
• 选中该分组后，删除所有和该分组有重叠对象的其他分组，重复上述步骤直到没有可选分组
  该方法时间复杂度仅为O(M*N)，大部分场景下可以得到最优解80%以上的结果，适合性能优先的场景。

内容的提问来源于stack exchange，提问作者nik