每日算法 — 使用java实现分数规划：最优比率问题的二分答案与参数搜索

算法概述

分数规划（Fractional Programming）是一类处理最优比率问题的经典算法框架。它解决的是形如 $\max \frac{\sum a_i x_i}{\sum b_i x_i}$ 或 $\min \frac{\sum a_i x_i}{\sum b_i x_i}$ 的优化问题，其中 $x_i \in {0, 1}$ 表示是否选择第 $i$ 个元素。这类问题直接求解非常困难，但分数规划通过二分答案 + 判定的技巧，将其转化为可判定的问题，从而在 $O(\log(\text{精度}) \cdot \text{判定复杂度})$ 内求解。

核心思想

Dinkelbach算法

分数规划的核心是 Dinkelbach 迭代算法：

假设要最大化 $\frac{A}{B}$，其中 $A = \sum a_i x_i$，$B = \sum b_i x_i > 0$。

1. 猜测一个比率值 $\lambda$
2. 构造判定问题：是否存在选择方案使得 $\frac{A}{B} \geq \lambda$？
3. 等价于判断是否存在方案使得 $A – \lambda B \geq 0$，即 $\sum (a_i – \lambda b_i) x_i \geq 0$
4. 令 $c_i = a_i – \lambda b_i$，问题转化为：能否选择一组元素使得 $\sum c_i \geq 0$？

如果判定问题的答案是”是”，说明最优比率 $\geq \lambda$，可以尝试更大的 $\lambda$；否则需要减小 $\lambda$。

二分答案框架

low = 0, high = max_possible_ratio
while (high - low > eps):
    mid = (low + high) / 2
    if check(mid):  // 判定是否存在方案使得比率 >= mid
        low = mid
    else:
        high = mid
return low

Java 完整实现

import java.util.*;

/**
 * 分数规划（Fractional Programming）完整实现
 * 包含多种经典模型：0-1分数规划、最优比率生成树、最优比率环等
 */
public class FractionalProgramming {

    static final double EPS = 1e-8;

    /**
     * 模型1：0-1分数规划
     * 从n个物品中选择恰好k个，使得 (sum a_i) / (sum b_i) 最大
     * 
     * 判定：给定lambda，是否存在k个物品使得 sum(a_i - lambda * b_i) >= 0
     */
    static double zeroOneFractionalPlanning(double[] a, double[] b, int k) {
        int n = a.length;
        double low = 0, high = 1e9;

        for (int iter = 0; iter < 60; iter++) { // 二分60次足够精度
            double mid = (low + high) / 2;

            // 计算每个物品的 c_i = a_i - mid * b_i
            double[] c = new double[n];
            for (int i = 0; i < n; i++) {
                c[i] = a[i] - mid * b[i];
            }

            // 排序，取前k大的c_i
            Arrays.sort(c);
            double sum = 0;
            for (int i = n - 1; i >= n - k; i--) {
                sum += c[i];
            }

            // 如果前k大的和 >= 0，说明可以达到mid
            if (sum >= 0) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return low;
    }

    /**
     * 模型2：最优比率生成树
     * 在带权图中选一棵生成树，使得 (sum 边权a) / (sum 边权b) 最大
     * 
     * 判定：给定lambda，是否存在生成树使得 sum(a_e - lambda * b_e) >= 0
     * 即求最大生成树，判断最大生成树的权和是否 >= 0
     */
    static class Edge implements Comparable<Edge> {
        int u, v;
        double a, b; // 两种权值
        double c;    // a - lambda * b

        Edge(int u, int v, double a, double b) {
            this.u = u; this.v = v; this.a = a; this.b = b;
        }

        @Override
        public int compareTo(Edge other) {
            return Double.compare(other.c, this.c); // 按c降序，用于Kruskal最大生成树
        }
    }

    static int[] parent;

    static int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    static boolean unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        parent[x] = y;
        return true;
    }

    static double optimalRatioSpanningTree(int n, List<Edge> edges) {
        double low = 0, high = 1e9;

        for (int iter = 0; iter < 60; iter++) {
            double mid = (low + high) / 2;

            // 计算 c = a - mid * b
            for (Edge e : edges) {
                e.c = e.a - mid * e.b;
            }

            // Kruskal求最大生成树
            Collections.sort(edges);
            parent = new int[n + 1];
            for (int i = 1; i <= n; i++) parent[i] = i;

            double treeSum = 0;
            int count = 0;
            for (Edge e : edges) {
                if (unite(e.u, e.v)) {
                    treeSum += e.c;
                    count++;
                }
            }

            // 如果能形成生成树且权和 >= 0
            if (count == n - 1 && treeSum >= -EPS) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return low;
    }

    /**
     * 模型3：最优比率环
     * 在有向图中找一个环，使得环上 (sum 点权a) / (sum 边权b) 最大
     * 
     * 判定：给定lambda，是否存在环使得 sum(a_v - lambda * b_e) >= 0
     * 转化为判断图中是否存在正权环，可用SPFA检测
     */
    static class GraphEdge {
        int to;
        double a, b;
        GraphEdge(int to, double a, double b) {
            this.to = to; this.a = a; this.b = b;
        }
    }

    static double optimalRatioCycle(int n, List<GraphEdge>[] graph, double[] nodeA) {
        double low = 0, high = 1e9;

        for (int iter = 0; iter < 60; iter++) {
            double mid = (low + high) / 2;

            // 建图：边权 = a_v - mid * b_e (到达点的a值 - mid * 边权b)
            // 检测是否存在正权环
            double[] dist = new double[n + 1];
            int[] cnt = new int[n + 1];
            boolean[] inQueue = new boolean[n + 1];
            Queue<Integer> queue = new LinkedList<>();

            // 虚拟源点连接所有点
            for (int i = 1; i <= n; i++) {
                dist[i] = 0;
                cnt[i] = 0;
                inQueue[i] = true;
                queue.offer(i);
            }

            boolean hasPositiveCycle = false;
            while (!queue.isEmpty() && !hasPositiveCycle) {
                int u = queue.poll();
                inQueue[u] = false;

                for (GraphEdge e : graph[u]) {
                    int v = e.to;
                    double w = nodeA[v] - mid * e.b;
                    if (dist[v] < dist[u] + w) {
                        dist[v] = dist[u] + w;
                        cnt[v] = cnt[u] + 1;
                        if (cnt[v] >= n) {
                            hasPositiveCycle = true;
                            break;
                        }
                        if (!inQueue[v]) {
                            inQueue[v] = true;
                            queue.offer(v);
                        }
                    }
                }
            }

            if (hasPositiveCycle) {
                low = mid;
            } else {
                high = mid;
            }
        }

        return low;
    }

    /**
     * Dinkelbach迭代法（更高效的收敛方式）
     * 对于0-1分数规划，Dinkelbach通常比二分法收敛更快
     */
    static double dinkelbach(double[] a, double[] b, int k) {
        int n = a.length;
        double lambda = 0; // 初始猜测

        for (int iter = 0; iter < 100; iter++) {
            double[] c = new double[n];
            for (int i = 0; i < n; i++) {
                c[i] = a[i] - lambda * b[i];
            }

            // 按c排序，取前k个
            Integer[] idx = new Integer[n];
            for (int i = 0; i < n; i++) idx[i] = i;
            Arrays.sort(idx, (i, j) -> Double.compare(c[j], c[i]));

            double sumA = 0, sumB = 0;
            for (int i = 0; i < k; i++) {
                sumA += a[idx[i]];
                sumB += b[idx[i]];
            }

            double newLambda = sumA / sumB;
            if (Math.abs(newLambda - lambda) < EPS) {
                return newLambda;
            }
            lambda = newLambda;
        }

        return lambda;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("=== 分数规划演示 ===\n");

        // 0-1分数规划示例
        System.out.println("模型1：0-1分数规划");
        double[] a = {10, 20, 30, 40, 50};
        double[] b = {2, 3, 5, 7, 11};
        int k = 3;
        double ans1 = zeroOneFractionalPlanning(a, b, k);
        double ans1d = dinkelbach(a, b, k);
        System.out.printf("二分法结果: %.8f%n", ans1);
        System.out.printf("Dinkelbach结果: %.8f%n%n", ans1d);

        // 最优比率生成树示例
        System.out.println("模型2：最优比率生成树");
        int n = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(1, 2, 3, 1));
        edges.add(new Edge(1, 3, 2, 2));
        edges.add(new Edge(2, 3, 4, 1));
        edges.add(new Edge(2, 4, 1, 3));
        edges.add(new Edge(3, 4, 5, 2));
        double ans2 = optimalRatioSpanningTree(n, edges);
        System.out.printf("最优比率: %.8f%n%n", ans2);

        System.out.println("分数规划的核心是将复杂的比率优化问题转化为可判定的线性问题，");
        System.out.println("通过二分答案或Dinkelbach迭代高效求解。");
    }
}

复杂度分析

Dinkelbach 算法通常收敛很快（常数次迭代），实际效率往往高于二分法。

经典应用场景

1. 资源分配：在有限预算下最大化收益/成本比
2. 网络优化：最小化传输时延/带宽比
3. 投资组合：最大化收益/风险比（Sharpe比率）
4. 任务调度：最小化完成时间/资源消耗比
5. 图论问题：最优比率路径、最优比率流等

扩展：多目标分数规划

当涉及多个比率需要同时优化时，可以引入参数化搜索或帕累托最优概念，结合线性规划求解。分数规划的框架具有很强的扩展性，是处理比率优化问题的通用利器。