Здравствуйте, subdmitry, Вы писали:

S>Можно и еще соптимизировать. Заметим, что если какие-то числа были получены на i-м шаге алгоритма, и к ним на i+1 шаге были прибвалены все возможные числа, то на i+2 шаге такое число уже можно не обрабанывать. Соответственно, можно просто помнить все числа, полученные на каком-то шаге, например, в списке, потом на следующем шаге создавать новый список чисел, которые еще не встречались и так далее. Это уже фактически дает сложность O(X).

Остается только вопрос, как выбирать верхнюю и нижнюю границу массива. В принципе можно заметить, что для положительные искомые числа могут быть получены так, что все промежуточные суммы будут положительными, и наоборот, отрицательные числа получены так, что все промежуточные суммы отрицательны. С ограничением по максимуму (какой брать максимальный модуль допустимых чисел) все тоже просто — искомые числа можно получить так, что промежуточные суммы вылетят не более чем на модуль максимального из слагаемых от искомого числа. Соответственно, сложность получается вроде O(|X|+max|ai|). Мнэ. Или все-таки возможна ситуация, когда алгоритм делает очень много шагов, попадающих на уже занятые ячейки? Что-то я не соображу.

Подскажите алгоритм для следующей задачи

имеются некоторые числа(например -7, +6, -6, + 7, +13)

Нужно определить какое минимальное количесво этих чисел нужно взять (с повторением) что б получить число X
(например для X = 4 это 5: 4 = 6 + 6 — 7 — 7 + 6)

Обычный bfs вижу, но что есть пооптимальнее ?

Спасибо

Здравствуйте, _defrager, Вы писали:

_>Подскажите алгоритм для следующей задачи

_>имеются некоторые числа(например -7, +6, -6, + 7, +13)

_>Нужно определить какое минимальное количесво этих чисел нужно взять (с повторением) что б получить число X
_>(например для X = 4 это 5: 4 = 6 + 6 — 7 — 7 + 6)

Динамическое программирование на каждом новом шаге считаете какие у вас могут получится суммы если использовать ai или не использовать.
0. {0}
1. {0, a1}
2. {0, a1, a1+a2, a2}
...
всегда достаточно держать только current step array и элементы использованные для каждого числа, либо хранить историю — но тогда память...

Здравствуйте, zubr, Вы писали:

Z>Здравствуйте, _defrager, Вы писали:

_>>Подскажите алгоритм для следующей задачи

_>>имеются некоторые числа(например -7, +6, -6, + 7, +13)

_>>Нужно определить какое минимальное количесво этих чисел нужно взять (с повторением) что б получить число X
_>>(например для X = 4 это 5: 4 = 6 + 6 — 7 — 7 + 6)

Z>Динамическое программирование на каждом новом шаге считаете какие у вас могут получится суммы если использовать ai или не использовать.
Z>0. {0}
Z>1. {0, a1}
Z>2. {0, a1, a1+a2, a2}
Z>...
Z>всегда достаточно держать только current step array и элементы использованные для каждого числа, либо хранить историю — но тогда память...

Так не выйдет, т.к. каждый ai можно использовать по несколько раз. Лучше динамически строить по количеству используемых слагаемых:
{}
{a1 a2 ... an}
{2a1 a1+a2 ... a1+an a2+a1 2a2 ...}
...
Так и сумма быстрее найдется, да и будет уверенность, что с меньшим числом слагаемых нельзя.

Здравствуйте, zubr, Вы писали:

Z>Здравствуйте, _defrager, Вы писали:

_>>Подскажите алгоритм для следующей задачи

_>>имеются некоторые числа(например -7, +6, -6, + 7, +13)

_>>Нужно определить какое минимальное количесво этих чисел нужно взять (с повторением) что б получить число X
_>>(например для X = 4 это 5: 4 = 6 + 6 — 7 — 7 + 6)

Z>Динамическое программирование на каждом новом шаге считаете какие у вас могут получится суммы если использовать ai или не использовать.
Z>0. {0}
Z>1. {0, a1}
Z>2. {0, a1, a1+a2, a2}
Z>...
Z>всегда достаточно держать только current step array и элементы использованные для каждого числа, либо хранить историю — но тогда память...
Тогда лучше с конца идти.
Узел X. потомки — {x-a(n)...x+a(n)), для каждого из потомков считать своих потомков, все циклические ветки убивать. Оставлять только те ветки, котороые приближают результат к 0.

Здравствуйте, vadimcher, Вы писали:

V>Так не выйдет, т.к. каждый ai можно использовать по несколько раз. Лучше динамически строить по количеству используемых слагаемых:
V>{}
V>{a1 a2 ... an}
V>{2a1 a1+a2 ... a1+an a2+a1 2a2 ...}

Это и будет чистый brute force. Чтобы сделать из него динамическое программирование, надо учитывать, что некоторые числа получаются как суммы разными способами, например, a+b и b+a, а так же более сложными. Для этого можно завести массив, захватывающий неких разумный диапазон чисел, и пихать в него последнее добавленое слагаемое (если оно 0, то такое число еще не было получено). На каждом шаге алгоритма добавляем к каждой заполненой ячейке массива все возможные числа и записываем новые числа в новые ячейки, но только в том случае, если эта ячейка еще не заполнена. И так пока не доберемся до нужного числа. После этого делаем бэктрекинг, вычитам из последней суммы число, лежащее в массиве, получаем новую сумму, и так пока не доберемся до нуля.

Здравствуйте, subdmitry, Вы писали:

S>Это и будет чистый brute force. Чтобы сделать из него динамическое программирование, надо учитывать, что некоторые числа получаются как суммы разными способами, например, a+b и b+a, а так же более сложными. Для этого можно завести массив, захватывающий неких разумный диапазон чисел, и пихать в него последнее добавленое слагаемое (если оно 0, то такое число еще не было получено). На каждом шаге алгоритма добавляем к каждой заполненой ячейке массива все возможные числа и записываем новые числа в новые ячейки, но только в том случае, если эта ячейка еще не заполнена. И так пока не доберемся до нужного числа. После этого делаем бэктрекинг, вычитам из последней суммы число, лежащее в массиве, получаем новую сумму, и так пока не доберемся до нуля.

Можно и еще соптимизировать. Заметим, что если какие-то числа были получены на i-м шаге алгоритма, и к ним на i+1 шаге были прибвалены все возможные числа, то на i+2 шаге такое число уже можно не обрабанывать. Соответственно, можно просто помнить все числа, полученные на каком-то шаге, например, в списке, потом на следующем шаге создавать новый список чисел, которые еще не встречались и так далее. Это уже фактически дает сложность O(X).

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, vadimcher, Вы писали:

V>>Так не выйдет, т.к. каждый ai можно использовать по несколько раз. Лучше динамически строить по количеству используемых слагаемых:
V>>{}
V>>{a1 a2 ... an}
V>>{2a1 a1+a2 ... a1+an a2+a1 2a2 ...}

S>Это и будет чистый brute force. Чтобы сделать из него динамическое программирование, надо учитывать, что некоторые числа получаются как суммы разными способами, например, a+b и b+a, а так же более сложными. Для этого можно завести массив, захватывающий неких разумный диапазон чисел, и пихать в него последнее добавленое слагаемое (если оно 0, то такое число еще не было получено). На каждом шаге алгоритма добавляем к каждой заполненой ячейке массива все возможные числа и записываем новые числа в новые ячейки, но только в том случае, если эта ячейка еще не заполнена. И так пока не доберемся до нужного числа. После этого делаем бэктрекинг, вычитам из последней суммы число, лежащее в массиве, получаем новую сумму, и так пока не доберемся до нуля.

Нет, ну разумеется имелось в виду с оптимизацией --, т.е., например, не надо считать a1+a2, а затем a2+a1. Я имел в виду подход в принципе, т.е. динамику делать не по добавлению элементов один за одним, а по числу слагаемых.

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, subdmitry, Вы писали:

S>>Можно и еще соптимизировать. Заметим, что если какие-то числа были получены на i-м шаге алгоритма, и к ним на i+1 шаге были прибвалены все возможные числа, то на i+2 шаге такое число уже можно не обрабанывать. Соответственно, можно просто помнить все числа, полученные на каком-то шаге, например, в списке, потом на следующем шаге создавать новый список чисел, которые еще не встречались и так далее. Это уже фактически дает сложность O(X).

S>Остается только вопрос, как выбирать верхнюю и нижнюю границу массива. В принципе можно заметить, что для положительные искомые числа могут быть получены так, что все промежуточные суммы будут положительными, и наоборот, отрицательные числа получены так, что все промежуточные суммы отрицательны. С ограничением по максимуму (какой брать максимальный модуль допустимых чисел) все тоже просто — искомые числа можно получить так, что промежуточные суммы вылетят не более чем на модуль максимального из слагаемых от искомого числа. Соответственно, сложность получается вроде O(|X|+max|ai|). Мнэ. Или все-таки возможна ситуация, когда алгоритм делает очень много шагов, попадающих на уже занятые ячейки? Что-то я не соображу.


Приблизительно это я и имел в виду под bfs который у меня уже получился... Хотелось что-то еще быстрее.
Все равно спасибо

Здравствуйте, _defrager, Вы писали:

_>Приблизительно это я и имел в виду под bfs который у меня уже получился... Хотелось что-то еще быстрее.

Можно подумать на эту тему, только тогда пожалуйста поподробнее. Какие примерно значения имеют эти дельты и сколько их обычно? Какова величина Х? Каковы временные-железячные требования к алгоритму (если он будет работать за доли секунды на пентиуме, это устроит?) Устроит ли нахождение хорошего, но не вполне оптимального решения или это не годится категорически?

Здравствуйте, subdmitry, Вы писали:

S>Можно подумать на эту тему, только тогда пожалуйста поподробнее. Какие примерно значения имеют эти дельты и сколько их обычно? Какова величина Х? Каковы временные-железячные требования к алгоритму (если он будет работать за доли секунды на пентиуме, это устроит?) Устроит ли нахождение хорошего, но не вполне оптимального решения или это не годится категорически?

Аффтар, что-то вы молчите. А тут еще явно есть чего покопать, но без каких-то примерных представлений о реально встречающихся в вашей задаче числах это сложно. Рискну все-таки предложить такую оптимизацию, имеющую смысл когда X по модулю много больше дельт. В этом случае, как несложно заметить, сумма будет составлена большим количеством самого большого по модулю слагаемого одного знака с X и некоторым небольшим количеством других слагаемых. Чтобы ускорить поиск, можно применять ту же схему, что и раньше, но при каждом получении нового числа очередной серии смотреть, не является ли разность между этим числом и X кратной самого большого (по модулю) из дельт. Естественно, на очередном шаге может возникнуть одновременно несколько таких чисел и надо брать наибольшее (тогда понадобиться наименьшее количество слагаемых).

Так же хочу поправиться. Ранее я писал:

S>С ограничением по максимуму (какой брать максимальный модуль допустимых чисел) все тоже просто — искомые числа можно получить так, что промежуточные суммы вылетят не более чем на модуль максимального из слагаемых от искомого числа.

Это не верно. Контрпример — возьмем X=1 и a={11 -3}. Схема генерации с минимальным вылетом вверх получается такая (числа в скобках это временная сумма): 11 -3 -3 -3 (2) 11 (13) -3 -3 -3 -3 (1). То есть вылет получается на 13, что больше X+max(ai)=1+11=12. Видно, что сделать вылет меньше нельзя. Вопрос о том, что брать как верхнюю грань, отсекающую лишний поиск, не так прост. Ну, кто сообразит, сколько тут должно быть? Я как следующее предположение рискну выдвинуть |X|+sum|ai|.

Здравствуйте, subdmitry, Вы писали:

S>Это не верно. Контрпример — возьмем X=1 и a={11 -3}. Схема генерации с минимальным вылетом вверх получается такая (числа в скобках это временная сумма): 11 -3 -3 -3 (2) 11 (13) -3 -3 -3 -3 (1). То есть вылет получается на 13, что больше X+max(ai)=1+11=12. Видно, что сделать вылет меньше нельзя. Вопрос о том, что брать как верхнюю грань, отсекающую лишний поиск, не так прост. Ну, кто сообразит, сколько тут должно быть? Я как следующее предположение рискну выдвинуть |X|+sum|ai|.

Нашел. Для максимального по модулю вылета (и ограничении снизу 0-м) годится оценка в |Х|+|mах(-ai)|+|max(ai)|. То есть сумма модуля максимально отрицательного элемента и максимального положительного.

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, subdmitry, Вы писали:

S>>Это не верно. Контрпример — возьмем X=1 и a={11 -3}. Схема генерации с минимальным вылетом вверх получается такая (числа в скобках это временная сумма): 11 -3 -3 -3 (2) 11 (13) -3 -3 -3 -3 (1). То есть вылет получается на 13, что больше X+max(ai)=1+11=12. Видно, что сделать вылет меньше нельзя. Вопрос о том, что брать как верхнюю грань, отсекающую лишний поиск, не так прост. Ну, кто сообразит, сколько тут должно быть? Я как следующее предположение рискну выдвинуть |X|+sum|ai|.

S>Нашел. Для максимального по модулю вылета (и ограничении снизу 0-м) годится оценка в |Х|+|mах(-ai)|+|max(ai)|. То есть сумма модуля максимально отрицательного элемента и максимального положительного.

Спасибо, Дмитрий.
У меня получилось решить с помощью прямого и обратного поиска — вначале строил какие комбинации можно получить от X а потом от 0 — дало прирост скорости в 2 раза.