01 分数规划
在 x_i∈{0,1} 上最大化 Σa_i x_i / Σb_i x_i;参数化权值 a_i-λb_i,把比值判定化为 0/1 优化。标签 数学 / 分数规划 / 01 分数规划 / 二分答案 / 最优化
定义
这是 分数规划 在 时的特例。设 ,,且 。对
求
参数化判定
对 ,令
分数规划的判定给出
因此二分 时,每次只需解一个以 为权值的 0/1 优化问题。
无其他约束
若 ,则 可逐项选取。记 。若存在 ,取所有这样的项;否则取 最大的一项。于是
后一支至少选一项,保证 。
带组合约束
若 还带有其他约束, 就是权值为 的 0/1 优化问题。约束不同,判定算法也不同;例如 为生成树时,判定是带参数边权的最小生成树,见 Earthquake。
常见误解
- 无约束时只取正项;若所有 ,空集不满足 ,必须至少选一项。
- 忽略 :分母可能为零, 的可行域需要单独处理。
- 认为一次排序可以复用:权值 随 改变,每次判定都要按当前 重新比较。
- 把 当成最终答案:它只说明存在比值不低于 的 01 向量。
- 把 01 分数规划直接当成 01 背包:背包只是约束 的一种;判定时物品价值变为 。