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

Я пытаюсь реализовать алгоритм из этого вопроса: Нужна идея для решения этой алгоритмической головоломки, но мне не хватает некоторого пограничного случая, из-за которого мой код переходит в бесконечный цикл. Я могу исправить это, сделав некоторые косметические изменения, но это показывает, что я не понял алгоритм.

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

#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.

partitioning algorithm dynamic-programming greedy
person noman pouigt    schedule 11.10.2015    source источник
comment
Включите первые две повторяющиеся строки вывода и от одной до трех предшествующих ей. Угадывание: нижняя == граница == верхняя-1 ‹ раздел   -  person greybeard    schedule 11.10.2015

Ответы (1)


arrow_upward
1
arrow_downward

У вас есть пара ошибок:

  • во время бинарного поиска ваш тест while должен быть 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. После цикла for у вас должно быть выражение:

    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;
}
person sve    schedule 11.10.2015