деление целое на k частей

Question

Я программирую в java, и мне нужно сформулировать алгоритм. Требования алгоритма являются:

• У нас есть 3 целочисленных переменных n, m, k;
• Мы хотим разделить n Into k части так, чтобы сумма k -части равна n и каждая часть представляет собой целое число между 1 и m.
• Мы хотим все возможные комбинации с допустимыми целыми числами.

Например, с входным набором:

n = 7; m = 3; k = 4 

мы имеем два различных комбинаций, которые мы можем сформулировать:

7 = 2 + 2 + 2 + 1 

и

7 = 3 + 2 + 1 + 1 

поблагодарить всех вас.

Answer 1

Идея подхода к обратному алгоритму (с рекурсией). Вы можете уменьшить параметры и получить решения для частичных решений, а затем проверить, есть ли у вас правильное решение.

public class Problem { 

    private static void algorithm(int n, int k, int m) { 
     algorithmRecursive(Collections.EMPTY_LIST, n, k, m, 1); 
    } 

    private static void algorithmRecursive(List<Integer> partial, int n, int k, int m, int min) { 
     if ((k > 0)) { 
      // Optimization 
      if ((n <= k * m) && (n >= k*min)){ 
       for (int i = min; i <= Math.min(m, n); i++) { 
        List<Integer> newPartial = new ArrayList<>(partial); 
        newPartial.add(i); 
        algorithmRecursive(newPartial, n - i, k - 1, m, i); 
       } 
      } 
     } else if (n == 0) { 
      // Right solution 
      System.out.println(partial); 
     } 
    } 

    public static void main(String[] args) { 
     algorithm(7,4,3); 
    } 
} 

Answer 2

Чтобы получить подсчет «числа делений» вы можете использовать Dynamic Programming, что следует рекурсивной формула:

D(0,0,j) = 1 
D(x,0,j) = 0  x > 0 
D(x,i,j) = 0  x < 0 or j<0 
D(x,i,j) = D(x-j,i-1,j) + D(x,i,j-1) 

Ответ обозначается D(n,k,m) является числом таких подразделений.
Сложность O(n*k*m)

Java код:

public static int numDivisions(int n, int m, int k) { 
    int[][][] D = new int[n+1][k+1][m]; 
    for (int j = 0; j < m; j++) { 
     for (int x = 0; x <= n; x++) { 
      D[x][0][j] = 0; 
     } 
     D[0][0][j] = 1; 
    } 
    for (int i = 1; i <= k; i++) { 
     for (int x = 0; x <= n; x++) { 
      for (int j = 0; j < m; j++) { 
       D[x][i][j] = 0; 
       if (j > 0) D[x][i][j] += D[x][i][j-1]; 
       if (x-j-1 >=0) D[x][i][j] += D[x-j-1][i-1][j]; 
      } 
     } 
    } 
    return D[n][k][m-1]; 
} 

Как примечание стороны, это похоже на stars and bars проблемы - но здесь порядок не имеет значения, а кроме того вы верхняя граница числа «звезды» в клетке.

Answer 3

Я считаю, что это можно сделать легко с рекурсией. Сначала проверьте, можете ли вы вообще делить n, то есть n<=m*k && n>=k, если нет, верните пустой массив.

Если он делится, последовательно выбирайте m' из диапазона [1..m] и выберите это как первое число, затем получите остальное рекурсивно для параметров n'=n-'m, m'=m', k'=k-1, а затем верните все результаты.

Рекурсия будет успешно останавливаться только на n=0 и k=0. Сложность времени должна быть такой же, как размер выпуска.