algorithm - 整数を最大値で均等に割ります

Question

次のアルゴリズムが必要です。

• 指定されたターゲット合計nと指定された制限mが与えられます。これらは両方とも正の整数です。
• 被加数ができるだけ少ないターゲット合計nの整数分割を見つけたいと考えています。
• 各被加数は制限m以下でなければなりません。
• 上記の制約の範囲内で、被加数はできるだけ互いに近づける必要があります。つまり、nをできるだけ均等に分割する必要があります。

したがって、たとえば、ターゲットの合計がn  = 80 で、各加数が最大で m  = 30 でなければならない場合、少なくとも 3 つの加数が必要であり、最も偶数のパーティションは26 + 27 + 27です。

どうやってそれを計算しますか？

Answer 1

まず、整数除算を使用して次の式で配列のサイズを取得します。

size = (variable + maximum - 1) / maximum

次に、配列に次の数式を入力します。

extra = variable % size;
value = variable / size;
for each array value, set to value + 1 as long as there's extra; 
    value when the extra goes to zero.

Answer 2

ただの QnD アルゴリズムとコード...未テスト。

 double n=107;
    double max = 22;
    int d = (int) Math.ceil(n/max);
    int[] result = new int[d];
    int res=0, i=0,iter=0;
    while(res!=n){
        iter= (int) Math.ceil(n/d);
        while(iter+res>n) iter--;
        res+=iter;
        result[i] = iter;
        System.out.println("i: " + i + " iter: " + iter + " sum: " +res);
        i++;
    }