Нужно построить алгоритм с временем работы 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";
}
Не могли бы вы объяснить, в чем ошибка в моем алгоритме?
Попробуйте вот этот алгоритм (рекурсия, использую бинарное дерево):
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 с клавиатуры.
Добрый день! Много прочитал в интернете статей на эту тему и не до конца понял как этот метод реализуетсяМожет есть блок схема или псевдокод...