Разложение числа на заданные слагаемые

[menket]

Добрый день.

Помогите, пожалуйста, решить задачу.

Есть не целое число N и есть множество C не целых чисел. Необходимо выявить все возможные комбинации, когда из одного или нескольких чисел множества C можно составить сумму, равную числу N.

[Brukvalub]

Переберите последовательно все конечные суммы тех элементов из C , которые не превосходят числа N.

[menket]

Brukvalub

Это самое простое, что можно сделать.

Я хотел бы узнать, есть ли более умные методы.

[AD]

Ничё не понимаю ... Что такое "сумма числа N"? Множество C предполагается конечным? "Не целых" означает "ни в коем случае не целых" или "не обязательно целых"? Типа нужно предложить необходимые и достаточные условия, когда число N является суммой чисел из C? То есть для данных C и N предложить алгоритм проверки? Или для данного C найти все N? или для N найти все C?

[Brukvalub]

menket писал(а):

Я хотел бы узнать, есть ли более умные методы

Например. можно по-умному организовать перебор, тогда объем работы уменьшится.

[menket]

AD

Подредактировал первое сообщение на предмет

Цитата:

Что такое "сумма числа N"?

.

Множество С конечное.
Не обязательно целых. Числа положительные.
Нужно сформировать наборы (подмножества) чисел из множества С, таких, которые составят число N при их суммировании.

Добавлено спустя 3 минуты 58 секунд:

Пример.
Число N = 10.
Множество C = {9, 1, 8, 2, 4, 5}.

Правильные подмножества: {9, 1}, {8, 2}, {1, 4, 5}, т.к. их сумма равна 10, т.е. числу N.

[AD]

Ну не знаю, ну берем первый элемент множества $C$, скажем, $c_1$, и рекурсивно решаем задачу для $N-c_1$, $C\setminus\{c_1\}$. Когда дорешаем - выбрасываем $c_1$ из $C$, и снова решаем задачу для $N$,$C\setminus\{c_1\}$.

Возможно, поможет предварительно отсортировать C по убыванию. ? Умнее пока не соображу.

[menket]

AD

Я примерно также и придумал. Другой вариант — посчитать суммы всех возможных сочетаний элементов множества C, и выбрать из них равные N.

[нг]

По-моему, это вариант задачи о рюкзаке (задачи о ранце). Туда смотрите…