Разделите целое число равномерно с максимальным [закрытым]

Мне нужен алгоритм для следующего:

  • Мне задана заданная целевая сумма n и заданный предел m . Это и целые положительные числа.
  • Я хочу найти целочисленное разбиение целевой суммы n, которая имеет как можно меньше слагаемых.
  • Каждое слагаемое должно быть меньше или равно пределу m .
  • В рамках вышеуказанных ограничений слагаемые должны быть как можно ближе друг к другу; то есть я хочу, чтобы n было разделено как можно более равномерно.

Так, например, если целевая сумма равна n  = 80, и каждое слагаемое должно быть не более m  = 30, тогда мне нужно как минимум три слагаемых, а самый четный раздел - 26 + 27 + 27 .

Как я могу это вычислить?

algorithm,math,integer-partition,

-1

Ответов: 2


4 принят

Во-первых, вы получаете размер массива со следующей формулой, использующей целочисленное деление:

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.

0

Просто алгоритм QdD и код ... непроверены.

 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++;
    }
Алгоритм, математика, целое-раздел,