Алгоритм на поиск количество слагаемых в С

Question

Уже несколько дней думаю как максимально эффективно это сделать, но пока в голове банальный перебор

Имею на входе

Числа вроде: 1 2 5 10 50 100

Потом суммы: 3 8 4 30

Хочу найти посчитать минимальное кол-во слагаемых из "Числа вроде" для поиска каждого числа из "Потом суммы"

то есть: на выходе должно быть соответсвенно четыре числа (ответ взято в [ ])

[ 2 ]   - потому что (1+2=3)
[ 3 ]   -            (1+2+5=8)
[ 2 ]   -            (2+2=4)
[ 3 ]   -            (10+10+10=30)

Суммы не могут быть отрицательными
диапазон - int(от 0 включительно) int max
чисел может быть больше чем сумм
суммы может и не быть - программа напишет что решения нет и перейдет к след числу.

Answer 1

Заводим массив целых A[] длиной Sum+1 для хранения минимальных количеств слагаемых для каждой суммы, инициализируем большим числом, нулевая ячейка = 0

Обходим массив номиналов. Для каждого номинала V проходим по ячейкам A.

Если A[i + V] больше, чем A[i]+1, то записываем в A[i + V] значение A[i]+1 - это означает, что сумму i+V выгоднее составить с использованием монеты V.

В конце А[Sum] содержит минимальное количество монет

Answer 2

Теория

Через t(j), 1 <= j <= n обозначим слагаемые которые составляют сумму. Пусть мы составили сумму s минимальным набором слагаемых из t(j). Уберем из набора одно слагаемое. Получится сумма s - t(j). Новый набор слагаемых для неё тоже минимальный, иначе возьмём набор меньшего размера, добавим к нему одно слагаемое, получим набор для s меньше того с которого начинали. Противоречие.

Обозначим через c(s) минимальное количество слагаемых нужное чтобы составить сумму s. Тогда верны такие соотношения:

c(s) = с(s - t(j)) + 1, если t(j) входит в минимальный набор
c(s) < с(s - t(j)) + 1, если t(j) не входит в минимальный набор

Чтобы вычислить c(s) надо попробовать удалять слагаемые по одному и брать минимальный результат:

c(s) = 1 + min(с(s - t(j)), 1 <= j <= n)

Формула выше не совсем честная: c(s) не определена если s < 0 и если сумму вообще нельзя составить. В обоих случах положим что c(s) = +inf. Формула станет верной всегда.

Последний штрих: c(0) = 0 - нулевую сумму составляем пустым набором слагаемых.

Практика

Бесконечность в программе на C будут представлять беззнаковые числа большие INT_MAX. Значение c(s) считаем последовательно от единицы до требуемой суммы. Значения хранятся с массиве cs. Последнее число из массива - ответ:

unsigned c(unsigned n, unsigned ts[/* n */], unsigned s) {
    unsigned *cs = malloc(sizeof(unsigned) * (s + 1));
    if (cs == NULL) {
       exit(1);
    }
    cs[0] = 0;
    for (unsigned i = 1; i <= s; ++i) {
        unsigned min_c = 1u + (unsigned)INT_MAX;
        for (unsigned j = 0; j < n; ++j) {
            unsigned t = ts[j];
            if (0 < t && t <= i) {
                unsigned c = cs[i - t];
                if (c < min_c) {
                    min_c = c;
                }
            }
        }
        cs[i] = min_c + 1;
    }
    unsigned c = cs[s];
    free(cs);
    return c;
}

Формат ввода не самый удобный для C: сложная функция read_list читает числа из одной строки в массив.

В функции c не используется VLA - большой массив таким образом не выделить, а нужен массив размером до 4 * 2^31 + 1 (8GB).

#include <ctype.h>
#include <limits.h>
#include <memory.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    unsigned size;
    unsigned capacity;
    unsigned *data;
} list_t;

void append(list_t *list, unsigned v) {
    if (list->capacity == list->size) {
        unsigned capacity = 2 * list->capacity + 1;
        unsigned *data = realloc(list->data, sizeof(unsigned) * capacity);
        if (data == 0) {
            exit(1);
        }
        list->capacity = capacity;
        list->data = data;
    }
    list->data[list->size++] = v;
}

bool skip_spaces() {
    for (; ; ) {
        int c = getc(stdin);
        if (c == EOF) {
            return false;
        }
        if (!isspace(c)) {
            ungetc(c, stdin);
            return true;
        }
        if (c == '\n' || c == '\r') {
            ungetc(c, stdin);
            return false;
        }
    }
}

void read_list(list_t *list) {
    do {
        unsigned n;
        if (scanf("%u", &n) != 1 || n > INT_MAX) {
            exit(1);
        }
        append(list, n);
    } while (skip_spaces());
}

unsigned c(unsigned n, unsigned ts[/* n */], unsigned s) {
    unsigned *cs = malloc(sizeof(unsigned) * (s + 1));
    if (cs == NULL) {
       exit(1);
    }
    cs[0] = 0;
    for (unsigned i = 1; i <= s; ++i) {
        unsigned min_c = 1u + (unsigned)INT_MAX;
        for (unsigned j = 0; j < n; ++j) {
            unsigned t = ts[j];
            if (0 < t && t <= i) {
                unsigned c = cs[i - t];
                if (c < min_c) {
                    min_c = c;
                }
            }
        }
        cs[i] = min_c + 1;
    }
    unsigned c = cs[s];
    free(cs);
    return c;
}

int main() {
    list_t terms = {0};
    read_list(&terms);
    printf("terms");
    for (unsigned i = 0; i < terms.size; ++i) {
        printf(" %u", terms.data[i]);
    }
    puts("\n");

    unsigned s;
    while (scanf("%u", &s) == 1 && s <= INT_MAX) {
        printf("sum %u -> ", s);
        unsigned c_ = c(terms.size, terms.data, s);
        if (c_ <= INT_MAX) {
            printf("%u", c_);
        } else {
            putc('?', stdout);
        }
        puts("");
    }
}

$ gcc -std=c11 -pedantic -Wall -Wextra -Werror -O3 shortest-sum.c

$ cat in1
1 2 5 10 50 100
3 8 4 30

$ ./a.out < in1
terms 1 2 5 10 50 100

sum 3 -> 2
sum 8 -> 3
sum 4 -> 2
sum 30 -> 3

$ cat in7
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
2147483647

$ time ./a.out < in7
terms 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

sum 2147483647 -> 46

real  0m33.661s
user  0m31.316s
sys   0m2.176s

БЛОГ НА HUSL

Алгоритм на поиск количество слагаемых в С

Ответы (2 шт):

Теория

Практика