Как разложить число на сумму других чисел?

Question

[Роман Назаркин]

Приветствую!

Вопрос следующий: К примеру, есть набор чисел (2, 3, 4, 5, 6) и какое-то произвольное число, такое, что n >=2. Так вот, нужно разложить это число на сумму вышеперечисленных(они могут повторяться в исходном наборе).

Пример: число 7 можем разложить как 3 + 4. Число 9 как 5 + 4. Число 11 разложим как 5 + 4 + 2.

Существуют ли подобные алгоритмы? Ну и пример на каком-либо языке, если есть, очень приветствуется.

Comments

[Oxoron]

Пусть modulo = остатку от деления n на 6. Пусть k= результат целочисленного деления n на 6. Короче, n = 6k + modulo.
IF modulo == 0: n = 6k = (6+6+6+...+6).
IF modulo == 1: n = 6k + 1 = 6(k-1) + 6 + 1 = 6(k-1) +7 = 6(k-1) + 5 + 2.
IF modul0 > 1: n = 6k+modulo.

Answer 1

[Армянское Радио]

Задача об упаковке рюкзака это называется. Дальше - в Википедию.

Answer 2

[Сергей]

Копайте в сторону динамического программирования
Задача о сумме подмножеств