Проблема с алгоритмом

303
21 мая 2017, 23:57

Нужно построить алгоритм с временем работы O(mn). На вход подается список положительных целых чисел a_1, a_2, ..., a_n и положительное целое m. Можно ли представить m как сумму некоторых из a_1, a_2, ..., a_n? Каждое a_i разрешается использовать не более одного раза. Мой код:

#include <iostream>
#include <vector>
int main() {
    size_t t = 0; // число, которое необходимо представить в виде суммы
    std::cin >> t;
    size_t n = 0;
    std::cin >> n; // количество вводимых положительных чисел
    std::vector<size_t> array(n); // массив, в котором хранятся введенные числа
    for (size_t i = 0; i != n; ++i)
        std::cin >> array[i];
    std::vector<size_t> solver(t + 1); // массив, в котором я храню последнее слагаемое в разложении числа
    for (size_t i = 0; i != n && array[i] <= t; ++i) {
        solver[array[i]] = array[i]; // инициализирую подходящие элементы
    }
    for (size_t i = 0; i != n; ++i) {
        size_t sum = array[i]; // sum - число, которое является слагаемым в разложении
        for (size_t k = t; k != sum; --k) {
            if (solver[k] == 0 && solver[k - sum] != 0) // если k-ое число 0, значит пока мы это число не получили суммой
                // и если k - sum не 0, значит k можно получить прибавлением sum, тогда оно последнее число в разложении k
                solver[k] = sum;
        }
    }
    if (solver[t]) // если это число не 0, то разложение получено
        std::cout << "YES\n";
    else
        std::cout << "NO\n";
}

Не могли бы вы объяснить, в чем ошибка в моем алгоритме?

Answer 1

Попробуйте вот этот алгоритм (рекурсия, использую бинарное дерево):

int check_tree(int a[], int i, int count_a, int sum, int m)
{
    if (i >= count_a)
    {
        return 0;
    }
    int new_sum = a[i] + sum;
    if (new_sum == m)
    {
        return 1;
    }
    if (check_tree(a, i + 1, count_a, sum, m))
    {
        return 1;
    }
    return check_tree(a, i + 1, count_a, new_sum, m);
}
int main()
{
    int m;
    int a[] = { 16, 20, 77, 40, 55, 30, 70, 80, 120, 150 };
    int count_a = 10;
    printf("type m: ");
    scanf("%d", &m);
    if (check_tree(a, 0, count_a, 0, m))
    {
        printf("\nSuccess!");
    }
    else
    {
        printf("\nFail!");
    }
    _getch();
    return 0;
}

Для простоты проверки я не стал делать ввод массива a с клавиатуры.

READ ALSO
Получить список всех доменов c++

Получить список всех доменов c++

Как получить список всех доменов? ну хотя бы на 1 ип

419
Реализация метода Хопфилда

Реализация метода Хопфилда

Добрый день! Много прочитал в интернете статей на эту тему и не до конца понял как этот метод реализуетсяМожет есть блок схема или псевдокод...

329
Как работает streambuf?

Как работает streambuf?

Странно, но на этот класс как-то мало описания в инете

285
Структуры С++ Проблема в создании

Структуры С++ Проблема в создании

У меня возникла,странная проблема при создании структуры

228