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是确切大小的子列表的数量Ky是长度的子列表的数量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 回答