algorithm - 在 p 组 q 成员中分配 n 个对象

Question

我无法找到这个确切问题的答案:

给定 n 个对象，n 至少为 2 的整数，我需要在 p 组之间平均分配它们，其中 p 大于或等于 2 且 n 大于或等于 p，其中“等于”的意思如下:每个组包含 q 成员； q 至少为 1。组的成员数量决定了该组的“权重”，因为 n 对象应该分布为更大的组(即更多的成员) ) 得到更多的对象。但是，每个组必须至少收到一个对象。

示例:给定 n=5 对象和两组 p_1 和 p_2 以及 q_1=1 和 q_2=9，p_1 得到 1 个对象，p_2 得到 4.

Answer 1

你的问题不是很清楚。你可能想要这个:

// add 1 to each group and subtract from n
for (int i = 0; i < p; ++i)
    group[i] = 1;
n -= p;

while (n > 0)
{
    // find i, such that q[i] / group[i] is maximum
    int imax = 0;
    double max = q[0] / group[0];
    for (int i = 1; i < p; ++i)
    {
        if (q[i] / group[i] > max)
        {
            max = q[i] / group[i];
            imax = i;
        }
    }
    ++group[imax];
    --n;
}

参见 https://en.wikipedia.org/wiki/D%27Hondt_method