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 M1 を追加して正しい数の配列 (N はリストの長さ、M はチームの最大サイズ) を取得し、アイテムがなくなるまですべての配列を反復処理してアイテムを追加します。

例 : 43 人の名前、最大チーム数 4 => 43 mod 4 + 1 = 11、3 のままなので、11 の配列 (4 の場合は 10、3 の場合は 1)

于 2012-01-12T14:38:31.710 に答える
2

リスト内のN項目数が で、サブリスト内の項目の最大数がKである場合、問題の解は線形ディオファントス方程式を解くことから得られます。

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

追加の制約あり

x > 0
y >= 0

は正確xなサイズのサブリストの数K、yは長さのサブリストの数ですK-1。

編集：方程式の係数は常に互いに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 に答える
2

I'm not going to write code for this, but

  1. If the list size is a multiple of the max team size, divide by team size to get the number of groups, all of max size, and stop.
  2. Integer-divide the list size by the max team size, then add one. That's the number of groups.
  3. Subtract the list size from that next higher multiple; that's the number of teams that are one less than the max size.

This obviously only works for inputs that are close to working out; it fails if the max team size is large compared to the size of the list.

于 2012-01-12T14:36:03.910 に答える
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 に答える