约束BX=0下最大化AX的标准求解算法是什么？

问题本质 #

这个问题属于单约束连续变量线性规划，有成熟的专属高效解法，复杂度仅为O(n log n)，远优于通用线性规划求解器的开销。

具体求解步骤 #

• 第一步：预处理零B值元素
  对所有满足B[i] = 0的下标i：由于它的取值不影响约束条件，为了最大化目标函数，只要A[i] > 0就直接令X[i] = 1，A[i] < 0就令X[i] = 0，这部分元素不需要参与后续计算。
• 第二步：分组排序
  把剩下的元素分成两组：
  • 正B组：所有B[i] > 0的元素，按A[i]/B[i]的比值从高到低排序
  • 负B组：所有B[i] < 0的元素，按A[i]/(-B[i])的比值从高到低排序
    排序逻辑为：每消耗1单位的B配额，优先选择能带来最高A收益的元素，保证全局最优。
• 第三步：贪心匹配配额
  我们需要找到一个非负数值S，使得正B组贡献的sum(B[i] * X[i]) = S，负B组贡献的sum(|B[i]| * X[i]) = S，刚好满足约束sum(B[i] * X[i]) = S - S = 0，同时目标函数取值最大。
  具体匹配规则：
  1. 对排序后的正B组，按顺序优先取X[i] = 1，累计得到前缀B和、前缀A和
  2. 对排序后的负B组，按顺序优先取X[i] = 1，累计得到前缀|B|和、前缀A和
  3. 找到最大的可行S，S不能超过正B组的最大总B和，也不能超过负B组的最大总|B|和。匹配过程中最多只有两个元素的X[i]取(0,1)之间的分数（一个在正B组，一个在负B组），其余元素均取0或1。

补充说明 #

通用线性规划求解器（比如单纯形法、内点法）也可以直接求解这个问题，只是对于这个单约束的特殊结构，上述贪心解法效率更高，适合n非常大的场景。你之前没找到适配方案，大概率是因为这个属于线性规划下的特例，通常不会单独放在背包问题分类里。

内容的提问来源于stack exchange，提问作者Carlos Pinzón