4

我有一个名单。

我想将此列表划分为指定大小的组。所有组应等于或小于指定大小，各组之间的组大小应尽可能相等，并尽可能接近指定大小。

什么算法（如果可能，请使用 Java 类伪代码！）确定最合适的组大小？

例如：

列表包含 13 个名称 - 最大团队规模 3。输出（组规模）：3、3、3、2、2

列表包含 13 个名称 - 最大团队规模 4。输出：4、3、3、3

列表包含 31 个名称 - 最大团队规模 5。输出：5、5、5、4、4、4、4

列表包含 31 个名称 - 最大团队规模 6。输出：6、5、5、5、5、5

列表包含 31 个名称 - 最大团队规模 10。输出：8、8、8、7

4

4 回答 4

4

这很简单。您计算结果N div M并添加 1 以获得正确的数组数量（N 是列表长度，M 是最大团队大小），然后迭代所有数组以添加项目，直到项目用完

示例：43 个名称，最大团队编号 4 => 43 mod 4 + 1 = 11，仍然是 3。所以 11 个数组（10 和 4 和 1 和 3）

于 2012-01-12T14:38:31.710 回答
2

我不会为此编写代码，但是

  1. 如果列表大小是最大团队大小的倍数，则除以团队大小以获得组数、所有最大大小，然后停止。
  2. 将列表大小除以最大团队大小的整数，然后加一。这就是组的数量。
  3. 从下一个更高的倍数中减去列表大小；这是比最大规模小一的团队数量。

这显然只适用于接近锻炼的输入；如果与列表的大小相比，最大团队规模较大，则会失败。

于 2012-01-12T14:36:03.910 回答
2

如果列表中的项目数是N并且子列表中的最大项目数是K，则问题的解决方案来自求解线性丢番图方程

K*x + (K-1)*y = N

有额外的限制

x > 0
y >= 0

其中x是确切大小的子列表的数量K，y是长度的子列表的数量K-1。

编辑：由于方程的系数总是彼此偏离，所以解决方案相当简单：

int m = (N+K-1)/K;
int x = N - (K-1)*m; // Number of "full" lists
int y = K*M - N;     // Number of off-by-one lists

示例 1：

N = 31, K = 5
m = (31+5-1)/5 = 7
x = 31 - (5-1)*7 = 3 // 3 lists of 5 items
y = 5*7 - 31 = 4     // 4 lists of 4 items

示例 2：

N = 32, K = 4
m = (32+4-1)/4 = 8
x = 32 - (4-1)*8 = 8 // 8 lists of 4 items
y = 4*8 - 32 = 0     // no lists of 3 items

在网上查找求解线性丢番图方程的算法——如果你对欧几里得算法有很好的理解，它并不复杂。没有约束的方程的解数是无限的，但是一旦添加了约束，您应该得到一个解。

于 2012-01-12T14:42:23.183 回答
0 
public class Q {
public static void q(int size, int maxTeamSize) {
    int numOfTeams = size / maxTeamSize;
    int mod = size % maxTeamSize;
    numOfTeams += (mod > 0) ? 1 : 0;
    System.out.print("\n(" + size + ":" + maxTeamSize + ")");
    for (int i = 0; i < numOfTeams; i++) {
        System.out.print(" " + (size / numOfTeams + ((i < mod) ? 1 : 0)));
    }
}

public static void main(String[] args) {
    q(13, 3);
    q(12, 4);
    q(31, 5);
    q(31, 6);
}
}
于 2012-01-12T15:29:14.953 回答