Получить разбиение числа из чисел заданного диапазона

[coll3ctor]

Доброго времени суток, господа!

В общем накрыла меня задача...
Имеется 7 чисел (будем говорить, массив чисел).
Вот они: $A=(10, 25, 50, 100, 200, 300, 1000)$
И задано число, в интервале от 90 до 9000. Необходимо получить его представление в виде суммы (разбиение) элементов заданного массива за 9 итераций (или операций).
То есть задают число 300, мы каким то магическим образом вычисляем, что 300 это 8*25 из массива и 100. То есть за 9 итераций нашли данное число. Но как это запрограммировать? Вообще, это решаемая задача?
===================================
Мои попытки решения.
Прежде всего, дабы не нагружать процессор, делаем проверки на принадлежность числа диапазону, затем проверяем, быть может заданное число это какой то элемент массива умноженный на 9. Затем...короче, поступают идеи в голову, пытаюсь высчитать на бумаге, но сразу же нахожу опровержение. В общем вот.

[gris]

Не понятно: то ли решить задачу за девять итераций (что понимается под одной итерацией?) или представить число в виде суммы девяти слагаемых?
У меня получилось так: $300=10+10+10+10+10+25+25+100+100$

[Shadow]

Если длина массива и число слагаемых зафиксировано, то можно выписать все возможные комбинации - их 5005. Возможные представления числа 300 в виде 9-ти слагаемых из массива:

$\\6\times 25+3 \times 50\\ 8\times 25+100\\ 5\times 10+3 \times 50 + 100\\ 5\times 10+2 \times 25 + 2\times 100$

[coll3ctor]

gris в сообщении #678291 писал(а):

Не понятно: то ли решить задачу за девять итераций (что понимается под одной итерацией?) или представить число в виде суммы девяти слагаемых?
У меня получилось так: $300=10+10+10+10+10+25+25+100+100$

В смысле да, по-математически: решить задачу 9 слагаемыми из массива чисел. При чём, с повторениями можно. Да, вот так, как вы указали.

-- Чт янв 31, 2013 20:10:58 --

Shadow в сообщении #678347 писал(а):

Если длина массива и число слагаемых зафиксировано, то можно выписать все возможные комбинации - их 5005. Возможные представления числа 300 в виде 9-ти слагаемых из массива:

$\\6\times 25+3 \times 50\\ 8\times 25+100\\ 5\times 10+3 \times 50 + 100\\ 5\times 10+2 \times 25 + 2\times 100$

Понятно. А как это запрогать?

Количество слагаемых фиксированно и сами они фиксированны

-- Чт янв 31, 2013 20:11:41 --

Прошу прощения, не девятью (9) слагаемыми, а семью (7). Скоко элементов массива, столькими и нужно. Прошу прощения :( не могу изменить первый пост свой.

[Shadow]

coll3ctor в сообщении #678453 писал(а):

Понятно. А как это запрогать

Я сделал самым дебильным способом:

Используется синтаксис Visual Basic

For X1 = 0 To 9
 For X2 = 0 To 9 - X1
  .........
     For x6 = 0 To 9 - X1 - X2 - x3 - x4 - x5
      x7 = 9 - X1 - X2 - x3 - x4 - x5
      S = 10 * X1 + 25 * X2 + 50 * x3 + 100 * x4 + 200 * x5 + 300 * x6 + 1000 * x7
...      

занес в clipboard, оттуда в excel, отсортировал....

[coll3ctor]

Shadow в сообщении #678491 писал(а):

coll3ctor в сообщении #678453 писал(а):

Понятно. А как это запрогать

Я сделал самым дебильным способом:

Используется синтаксис Visual Basic

For X1 = 0 To 9
 For X2 = 0 To 9 - X1
  .........
     For x6 = 0 To 9 - X1 - X2 - x3 - x4 - x5
      x7 = 9 - X1 - X2 - x3 - x4 - x5
      S = 10 * X1 + 25 * X2 + 50 * x3 + 100 * x4 + 200 * x5 + 300 * x6 + 1000 * x7
...      

занес в clipboard, оттуда в excel, отсортировал....

Тот, с кем мы сформировали это задание, очень не хочет, чтобы сервер нагружался. Хотя тут не так много будет. (это для игр, на сайте)

[Shadow]

Но это не программа, котороя будет работать постоянно. Запускаем одноразово, чтобы получить все возможные комбинации. Их можно хранить в файл, в БД. Всего 5005 записей. По 9 байта на запись. 45к спокойно можно и в памяти хранить. Для сервера даже смешно.
Иначе все равно придется решать диофантово уравнение с шестью неизвестными и без перебора не обойтись.
Но я вашу задачу не знаю и не могу советовать.

-- 31.01.2013, 20:20 --

5005 записей для 9 слагаемых. Для 7 еще меньше будет

[Deggial]

Задача имеет вид:
Заданы числа $a_1,...,a_n$, переменные $x_1,...,x_n\geqslant 0$, причем $x_1+...+x_n=A$ (у Вас $A=9$) и $a_1x_1+...+a_nx_n=B$, у Вас $B$ - входной параметр. Надо найти хотя бы одну энку $(x_1,...,x_n)$, удовлетворябщую условиям.
Это задача целочисленного линейного программирования в форме задачи распознавания. Простые общие методы решения - метод ветвей и границ или метод Гомори, кодится сложно и работать может долго.
Конкретно здесь, можно воспользоваться жадным алгоритмом для поиска решения. А если не получиться, то прогнать точный алгоритм и жадный алгоритм, найти все числа, для которых жадный алгоритм не сработал и обработать их в итоговом алгоритме отдельно
И еще, пользуясь конкретным списком коэффициентом, можно немного упростить уравнение. Например, все коэффициенты делятся на $5$, почти все - на $10$ и почти все - на $25$. С помощью этой информации можно немного упростить задачу.

Такое ощущение, что подобные темы уже были.