Динамическое программирование: Сбалансированный Partition

Question

Я хочу реализовать алгоритм динамического программирования для этой задачи: Вход: Данное устройство S неотрицательных чисел {S1 ....... Sn}

мы хотим разделите S на 2 подмножества S1 и S2 и минимизируйте | sum (S1) -sum (S2) |, затем разделим 2 подмножество таким же образом, остановимся, когда мы достигнем подмножества с 2 или 1 элементом(). Мы должны сохранить порядок элементов S).

пример: S = {1,2,2,3,4} Выход {{{1,2} {2}} {3,4}}

С помощью this article это моя реализация :

static String partition(int s[], int db,int fn) 
{ 
    int n = (fn-db) +1; 
    String res =""; 
    if (n<=2){ 
     res +="["; 
     for(int l =db ;l<=fn;l++) res+=s[l]; 
     res +="]"; 
     return res; 
    } 
    int[][] m= new int [n+1][3];     /* DP table for values */    
    int[][] d= new int [n+1][3];     /* DP table for dividers */ 
    int [] p = new int [n+1];     /* prefix sums array */ 
    int cost;        /* test split cost */ 
    int i,x = 0;        /* counters */ 

    p[0] = 0;        /* construct prefix sums */ 
    for (i=1; i<=n; i++) 
     p[i]=p[i-1]+s[(db-1)+i]; 

    for (i=1; i<=n; i++) 
     m[i][1] = p[i]; /* initialize boundaries */ 
     m[1][2] = s[db]; 


    for (i=2; i<=n; i++){     /* evaluate main recurrence */ 
      m[i][2] = Integer.MAX_VALUE; 
      for (x=1; x<=(i-1); x++) { 
       cost = Math.max(m[x][1], p[i]-p[x]); 
       if (m[i][2] > cost) { 
        m[i][2] = cost; 
        d[i][2] = db+(x-1); 
       } 
      } 
    } 
    return res +="["+partition(s,db,d[n][2])+partition(s,d[n][2]+1,fn)+"]"; 

} 

public static void main(String[] args) { 
    int []set ={2,1,1,1,5}; 
    System.out.print(partition(set,0,set.length-1)); 
} 

1. является ли моя реализация является хорошим или есть другое динамическое решение программирующий whitout рекурсивный вызов?

2. Я не могу рассчитать сложность этого алгоритма, я пытаюсь использовать теорему Мастера T (n) = aT (nb) + f (n), но теперь я не n/b размер каждой подзадачи для 2 рекурсивный вызов.

   3.Как мы можем сделать тот же раздел, если мы сможем изменить порядок элементов?

Answer 1

Подумайте об этом так: в самом худшем случае, у вас есть массив, где каждый индекс я содержу значение 2 ^я. В этом случае раскол уменьшает длину на единицу, что означает, что глубина рекурсии линейна по n. На каждом уровне вы выполняете O (n), поэтому общая сложность - O (n). К счастью, такие массивы будут очень короткими на практике, потому что мы обычно не рассматриваем такие огромные числа, поэтому производительность в реальном мире будет в целом лучше. Когда весы несколько сбалансированы, вы должны иметь производительность O (n log n).

Что касается первого вопроса, я не уверен, что вы имеете в виду «хороший».

EDIT: Вы можете сделать более эффективным алгоритм, выполнив двоичный поиск в местоположении, в котором вы хотите разделить массив. Это возможно, потому что заказ должен быть сохранен.