Могу ли я разделить массив в размерах K?

Question

Я пытаюсь реализовать алгоритм из этого вопроса: Need idea for solving this algorithm puzzle, но мне не хватает некоторого края, который вызывает мой код в бесконечном цикле. Я могу исправить это, сделав некоторые косметические изменения, но это показывает, что я не понял алгоритм.

Может кто-нибудь помочь мне, чего я не хватает?

#include <stdio.h> 

#define max(a, b) (((a)>(b))?(a):(b)); 
int get_max(int *a, int i, int size) 
{ 
    if (i >= size) 
     return 0; 
    return max(a[i], get_max(a, i+1, size)); 
} 

int get_sum(int *a, int i, int size) 
{ 
    if (i >= size) 
     return 0; 
    return a[i] + get_sum(a, i+1, size); 
} 

int get_partition(int *a, int size, int bound) { 
    int running_sum = 0; 
    int partitions = 0, i; 

    for (i=0;i<size;i++) { 
     if (a[i] + running_sum <= bound) { 
      running_sum += a[i]; 
     } else { 
      running_sum = 0; 
      running_sum += a[i]; 
      partitions++; 
     } 
    } 
    return partitions; 
} 

int foo(int *a, int size, int k) 
{ 
    int lower = get_max(a, 0, size); 
    int higher = get_sum(a, 0, size); 
    int partition; 

    while (lower < higher) { 
     int bound = (lower + (higher))/2; 

     partition = get_partition(a, size, bound); 
     printf("partition %d bound %d lower %d higher %d\n", partition, bound, lower, higher); 
     if (partition >= k) 
      lower = bound; 
     else 
      higher = bound; 
    } 
    return partition; 
} 

#define SIZE(a) sizeof(a)/sizeof(a[0]) 
int main(void) { 
    int a[] = {2, 3, 4, 5, 6}; 
    printf("%d\n", foo(a, SIZE(a), 3)); 
    return 0; 
} 

Выход:

partition 1 bound 13 lower 6 higher 20 
partition 2 bound 9 lower 6 higher 13 
partition 3 bound 7 lower 6 higher 9 
partition 3 bound 8 lower 7 higher 9 
partition 3 bound 8 lower 8 higher 9 
...last line keeps repeating. 

Answer 1

У вас есть несколько ошибок:

• во время бинарного поиска, в то время как ваш тест должен быть while (lower+1 < higher) { и не while (lower < higher) {. Вы вводите бесконечный цикл, когда lower = 8, higher = 9. На этом этапе ваш bound будет (lower+higher)/2=8, и вы обновите lower = bound, который ничего не изменит.
• в конце foo вы должны вернуть higher (не разделов) с момента двоичного поиска инварианта является то, что за то, что bound <= lower можно разделить массив в более чем k частей и bound >= higher вы можете разбить его на k или меньше.

• Ваш расчет get_partition неправ. Вы не принимаете в учетную запись последнюю группу разделов, поскольку вы обновляете только partitions, когда вы переполняете running_sum. После для цикла вы должны иметь заявление:

  if (running_sum > 0) 
      partitions++; 
  

Собираем все вместе:

#include <stdio.h> 

#define max(a, b) (((a)>(b))?(a):(b)); 
int get_max(int *a, int i, int size) 
{ 
    if (i >= size) 
     return 0; 
    return max(a[i], get_max(a, i+1, size)); 
} 

int get_sum(int *a, int i, int size) 
{ 
    if (i >= size) 
     return 0; 
    return a[i] + get_sum(a, i+1, size); 
} 

int get_partition(int *a, int size, int bound) { 
    int running_sum = 0; 
    int partitions = 0, i; 

    for (i=0;i<size;i++) { 
     if (a[i] + running_sum <= bound) { 
      running_sum += a[i]; 
     } else { 
      running_sum = 0; 
      running_sum += a[i]; 
      partitions++; 
     } 
    } 
    if (running_sum > 0) 
     partitions++; 
    return partitions; 
} 

int foo(int *a, int size, int k) 
{ 
    int lower = get_max(a, 0, size); 
    int higher = get_sum(a, 0, size); 
    int partition; 

    while (lower+1 < higher) { 
     int bound = (lower + (higher))/2; 

     partition = get_partition(a, size, bound); 
     printf("partition %d bound %d lower %d higher %d\n", partition, bound, lower, higher); 
     if (partition > k) 
      lower = bound; 
     else 
      higher = bound; 
    } 
    printf("partition %dlower %d higher %d\n", partition, lower, higher); 
    return higher; 
} 

#define SIZE(a) sizeof(a)/sizeof(a[0]) 
int main(void) { 
    int a[] = {2, 3, 4, 5, 6}; 
    printf("%d\n", foo(a, SIZE(a), 3)); 
    return 0; 
}