Разделите массив на разделы k contiguos таким образом, чтобы сумма максимального раздела была минимальной

Question

Здесь максимальное подмножество суммы является одним из k подмножеств, которые дают максимальную сумму например: arr = [10,5,3,7] и k = 2 возможно способы разделить arr на k подмножеств - {10, [5,3,7]}, {[10,5], [3,7}, {[10,5,3], 7} и {[10,5 ], [3,7} является оптимальным. Изменить: это эквивалентно https://www.codechef.com/DI15R080/problems/MINMAXTF

Answer 1

Это может быть решено с помощью динамического программирования :

Позволяет определить первый DP[n,m] быть оптимальным решением для разделения подмассива C[1..n] в m части. Где каждая часть имеет хотя бы один элемент.

DP[n,1] = sum(C1:Cn) 
DP[n,n] = max(C1:Cn) 
DP[n,m] = min(sum(Ck:Cn) + DP[k-1,m-1]) 
      where k goes from m to n 

Пояснение:
DP[n,1] - Базовый случай, когда количество разделов является 1 есть только один путь - все элементы слева (от 1 до п).
DP[n,n] - Каждый раз, когда количество разделов равно количеству элементов, оставшихся в массиве, существует только один законный способ его разделить - каждый элемент в другом разделе, поэтому раздел с максимальной суммой является максимальным элементом в массив.
DP[n,m] - Это основное решение. Мы не знаем точно, сколько элементов будет нашим следующим разделом, поэтому нам нужно пройти все опции и получить минимум от него.

Answer 2

Предположим, вы знаете, что ответ x, что означает, что сумма максимального подмножества равна x. Вы можете проверить это предположение жадным алгоритмом O (n). (Переместите массив слева направо и выберите элементы, пока сумма этого подмножества не станет ниже x). Теперь вы можете выполнить двоичный поиск по x и найти минимальное значение для x. Сложность этого алгоритма O (nlogn).

Answer 3

Разделение - это просто проблема грубой силы. Вы должны сосредоточиться на функции, чтобы свести к минимуму. Итак, вы должны свести к минимуму отклонение от среднего.

int sum_arr(int *arr,int size) 
{ 
    int res=0; 
    while (size-->0) 
     res+=*arr++; 
    return res; 
} 
int minimize(const int *array, int size) 
{ 
    int i,j,cur_i; 
    double dev, cur_min,avg=(double)sum_arr(array,size)/size; 

    for (i=1;i<size-1;i++) 
     { 
     dev=abs(avg-sum_arr(array,i)); 
     dev+=abs(avg-sum_arr(array+i,size-i); 
     if (dev<cur_min) 
     { 
       cur_min=dev; 
       cur_i=i; 
     } 
     } 
    return cur_i; 
} 

Простой код будет: (не проверено)

Answer 4

Это пример двоичного поиска в выборочном пространстве.

int min_max_sum(std::vector<int> & a){ 


    int n=a.size(); 

    long long high=0,low=0; 
    for (int i = 0; i < n; ++i) 
    { 
     high+=a[i]; 
     low=max(a[i],low); 
    } 

    while(low<=high){ 
     long long mid = (low+high)/2; 

     long long part_sum=0; 
     int parts=0; 
     for (int i = 0; i < n; ++i) 
     { 
      if (part_sum+a[i]>mid) 
      { 
       part_sum=0; 
       parts++; 
      }else{ 
       part_sum+=a[i]; 
      } 
     } 
     if (parts<=k) 
     { 
      low=mid+1; 
     }else{ 
      high=mid-1; 
     } 
    } 

    return high; 
} 

сложность: O (n log (сумма (массив))).

Но поскольку логрифмы экспоненциально лучше, чем линейные, эта сложность неплоха.

наихудшая сложность: O (n log (INT_MAX * n)) = O (32 n + n log (n)) = O (n log (n)).