最大余额法-解决计算占比不等于100的问题

简介

在使用 Echarts 可视化数据的时候，往往饼图中每块占比加和不等于100%，所以就有了最大余额法。下面是最大余额法的简介：

最大余额方法（英语：largest remainder method）又称数额制、汉弥尔顿法（英语：Hamilton method），是比例代表制投票制度下，一种议席分配的方法，相对于最高均数方法。

这个方法要求候选人透过名单形式参选。每个名单上的候选人数不能超过该选区的议席数。候选人在名单上是有排名顺序的。选民投票时，是投给整个名单，而不是单个候选人。

投票结束后，会用一个特定的“数额”（见下）去除所有有效票数。每个名单如果得票数达到这个数额的整数倍，就可以获得相应数量的议席。名单上的候选人按照名单上的排名顺序获得议席。

如果还有剩余的议席没分配完，就会看每个名单超过上一轮数额整数倍的票数（即“余额”）。这些剩余议席会根据各名单的余额大小顺序分配，所以这种方法叫做“最大余额法”。

https://www.cnblogs.com/CoderSilence/p/16775866.html

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package com.github.problem;

import java.util.Arrays;

/**
 * 最大余额法
 * 
 * @author shenjunyu
 */
public class LargestRemainderMethod {
    public static void main(String[] args) {
        int[] arr = {1, 4, 6, 8, 10, 88};
        System.out.println(Arrays.toString(getPercentValue(arr, 2)));
    }

    /**
     * 最大余额法，用于解决百分比不足100%或者超过100%的问题
     *
     * @param arr
     *            数组
     * @param idx
     *            索引
     * @param precision
     *            精度
     * @return 每一次计算的结果
     */
    public static double getPercentValue(int[] arr, int idx, int precision) {
        if ((arr.length - 1) < idx) {
            return 0;
        }
        // 求和
        double sum = 0;
        for (int j : arr) {
            sum += j;
        }
        if (sum == 0) {
            return 0;
        }
        // 10的2次幂是100，用于计算精度。
        double digits = Math.pow(10, precision);
        // 扩大比例100
        double[] votesPerQuota = new double[arr.length];
        for (int i = 0; i < arr.length; i++) {
            double val = arr[i] / sum * digits * 100;
            votesPerQuota[i] = val;
        }
        // 总数,扩大比例意味的总数要扩大
        double targetSeats = digits * 100;
        // 再向下取值，组成数组
        double[] seats = new double[arr.length];
        for (int i = 0; i < votesPerQuota.length; i++) {
            seats[i] = Math.floor(votesPerQuota[i]);
        }
        // 再新计算合计，用于判断与总数量是否相同,相同则占比会100%
        double currentSum = 0;
        for (double seat : seats) {
            currentSum += seat;
        }
        // 余数部分的数组:原先数组减去向下取值的数组,得到余数部分的数组
        double[] remainder = new double[arr.length];
        for (int i = 0; i < seats.length; i++) {
            remainder[i] = votesPerQuota[i] - seats[i];
        }
        while (currentSum < targetSeats) {
            double max = 0;
            int maxId = 0;
            for (int i = 0; i < remainder.length; ++i) {
                if (remainder[i] > max) {
                    max = remainder[i];
                    maxId = i;
                }
            }
            // 对最大项余额加1
            ++seats[maxId];
            // 已经增加最大余数加1,则下次判断就可以不需要再判断这个余额数。
            remainder[maxId] = 0;
            // 总的也要加1,为了判断是否总数是否相同,跳出循环。
            ++currentSum;
        }
        // 这时候的seats就会总数占比会100%
        return seats[idx] / digits;
    }

    /**
     * 最大余额法，用于解决百分比不足100%或者超过100%的问题
     *
     * @param arr
     *            数组
     * @param precision
     *            精度
     * @return 按照数组顺序排列的百分比
     */
    public static double[] getPercentValue(int[] arr, int precision) {
        double[] result = new double[arr.length];
        for (int i = 0; i < arr.length; i++) {
            result[i] = getPercentValue(arr, i, precision);
        }
        return result;
    }
}

结果

1
[0.85, 3.42, 5.13, 6.84, 8.55, 75.21]

完~