найти заданную сумму
Динамическое программирование
Создаешь массив из 10млн. флагов (по одному для каждого из значений суммы) и проходишься по нему 250 раз. Можно исхитриться использовать битовые маски для ускорения.
Что-то я не понял, как это решает задачу.
Жадный алгоритм (субоптимален)
Ну, если просто флаг, то оно решает задачу, можно ли такую сумму составить, а если надо точную комбинацию, то надо в каждой ячейке держать 250 флагов, ну, можно 249=).
И как быстро это решит задачу для числа 0x100000000000?
Автору топика надо было всего лишь для 0x186A0
Ну, если просто флаг, то оно решает задачу, можно ли такую сумму составить, а если надо точную комбинацию, то надо в каждой ячейке держать 250 флагов, ну, можно 249=).а не достаточно ли в каждой ячейке просто ссылку на предка хранить?
может, как-то так:
подготовка:
1. упорядочиваем массив по возрастанию.
2. идя с конца, набираем сумму, минимально большую требуемой, запоминаем индексы отобранных элементов.
далее, основной участок:
пусть есть какие-то уже отобранные индексы и известна сумма элементов массива по этим индексам.
1. проверяем для каждого из них, не уменьшится ли дельта между текущей суммой и требуемой, если элемент суммы поменять на соседний с ним в массиве. если уменьшится - меняем.
2. для каждого индекса смотрим, нельзя ли его заменть на два индекса так, чтобы получившаяся сумма отличалась от требуемой меньше, чем текущая. если можно, заменяем. опять же, пользуемся упорядоченностью массива чтобы уменьшить кол-во вариантов замены.
3. для каждых двух индексов смотрим, нельзя ли их заменить на один с тем же условием что и в 2. если можно, меняем.
если хотя бы в одном пункте из 1-3 было уменьшение разницы, повторяем их. если нет - значит, конец.
подготовка:
1. упорядочиваем массив по возрастанию.
2. идя с конца, набираем сумму, минимально большую требуемой, запоминаем индексы отобранных элементов.
далее, основной участок:
пусть есть какие-то уже отобранные индексы и известна сумма элементов массива по этим индексам.
1. проверяем для каждого из них, не уменьшится ли дельта между текущей суммой и требуемой, если элемент суммы поменять на соседний с ним в массиве. если уменьшится - меняем.
2. для каждого индекса смотрим, нельзя ли его заменть на два индекса так, чтобы получившаяся сумма отличалась от требуемой меньше, чем текущая. если можно, заменяем. опять же, пользуемся упорядоченностью массива чтобы уменьшить кол-во вариантов замены.
3. для каждых двух индексов смотрим, нельзя ли их заменить на один с тем же условием что и в 2. если можно, меняем.
если хотя бы в одном пункте из 1-3 было уменьшение разницы, повторяем их. если нет - значит, конец.
буду краток. херня
Достаточно. Можно даже не хранить массив, а держать только частичные суммы (резко сократится перебор, особенно при разреженных суммах, но будут накладки на доступ к элементам). Просто изначально были флаги, а размножить их - первое, что пришло на ум
предлагаю скомбинировать все указанные идеи.
0) предобработка - выбрасываем A[i] > Sum
1) Динамическое программирование. (оформляем поиск точного решения для некоторого интервала (0<x<N
Изначально достижим ноль. Добавляем в список (сортированный - значит дерево, но контейнер не важен) достижимые суммы. Берём меньшую, снова добавляем (без повторений достижимые суммы). До тех пор пока меньшее значение не выпадет за границы интервала. (отличается от классики списком достижимости вместо массивов флагов - на случай высокого разряжения
2) Не обязательно вычислять весь интервал. Можно составить интервал для a < S, и искать ответы в виде I[l]*k+I[m] - то есть поиск ответа по модулю одного из чисел. Возмоно это ускорит подбор в случае больших S (асимптотика худшего случая остаётся неизменной).
0) предобработка - выбрасываем A[i] > Sum
1) Динамическое программирование. (оформляем поиск точного решения для некоторого интервала (0<x<N
Изначально достижим ноль. Добавляем в список (сортированный - значит дерево, но контейнер не важен) достижимые суммы. Берём меньшую, снова добавляем (без повторений достижимые суммы). До тех пор пока меньшее значение не выпадет за границы интервала. (отличается от классики списком достижимости вместо массивов флагов - на случай высокого разряжения
2) Не обязательно вычислять весь интервал. Можно составить интервал для a < S, и искать ответы в виде I[l]*k+I[m] - то есть поиск ответа по модулю одного из чисел. Возмоно это ускорит подбор в случае больших S (асимптотика худшего случая остаётся неизменной).
> сумма нужна 100000
МНЕ ТОЖЕ!111
МНЕ ТОЖЕ!111
> сортированный - значит дерево
дерево не нужно, достаточно слияния сортированных списков.
дерево не нужно, достаточно слияния сортированных списков.
Решение с рекурсией пойдет?
Обозначим искомое число за N.
0) упорядочиваем массив по возрастанию, заодно смотрим, нет ли искомого числа среди заданных.
Пусть a_i — упорядоченный массив.
1) если самое минимальное больше, чем искомое пополам, значит сумму не получится найти.
2) проходим по массиву и для каждого индекса считаем и сохраняем сумму всех предыдущих чисел, эти суммы сохраняем. Идти можно не до конца массива, а пока сумма текущего элемента и минимального будет все еще меньше искомого. Пусть s_i — сумма a_k, для которых k<i (s_0 = 0, s_1 = a_0, s_n = a_(n-1)+s_(n-1. Так же обозначим через m такой индекс, что a_m+a_0 <= N, а a_(m+1)+a_0>N.
3) проверили, что сумма всех чисел с a_0 по a_m больше искомого. Потому что если меньше, то ничего не выйдет. Проверить надо что a_m+s_m > N.
4) если сумма текущего и минимального дала нужный результат, то выходим.
5) Если a_m и s_m в сумме дают N, тоже выходим.
6) Берем разницу (N-a_m) и пытаемся ее найти как сумму оставшихся чисел в массиве, рекурсивно вызывая эту же функцию.
7) Если нашли, то хорошо.
8) Если не нашли, то уменьшаем m на 1 и возвращаемся к пункту 3, пока m не дойдет до нуля.
По моим прикидкам получается сложность O(n^3) и максимальная глубина рекурсии n/2. Для n порядка 250, это реальные значения.
Обозначим искомое число за N.
0) упорядочиваем массив по возрастанию, заодно смотрим, нет ли искомого числа среди заданных.
Пусть a_i — упорядоченный массив.
1) если самое минимальное больше, чем искомое пополам, значит сумму не получится найти.
2) проходим по массиву и для каждого индекса считаем и сохраняем сумму всех предыдущих чисел, эти суммы сохраняем. Идти можно не до конца массива, а пока сумма текущего элемента и минимального будет все еще меньше искомого. Пусть s_i — сумма a_k, для которых k<i (s_0 = 0, s_1 = a_0, s_n = a_(n-1)+s_(n-1. Так же обозначим через m такой индекс, что a_m+a_0 <= N, а a_(m+1)+a_0>N.
3) проверили, что сумма всех чисел с a_0 по a_m больше искомого. Потому что если меньше, то ничего не выйдет. Проверить надо что a_m+s_m > N.
4) если сумма текущего и минимального дала нужный результат, то выходим.
5) Если a_m и s_m в сумме дают N, тоже выходим.
6) Берем разницу (N-a_m) и пытаемся ее найти как сумму оставшихся чисел в массиве, рекурсивно вызывая эту же функцию.
7) Если нашли, то хорошо.
8) Если не нашли, то уменьшаем m на 1 и возвращаемся к пункту 3, пока m не дойдет до нуля.
По моим прикидкам получается сложность O(n^3) и максимальная глубина рекурсии n/2. Для n порядка 250, это реальные значения.
хуета и точка тут: .
, и искать ответы в виде I[l]*k+I[m] - то есть поиск ответа по модулю одного из чисел.на практике мы заводим одно дерево.
В него пихаем два типа нодов - достижимые суммы и остатки по модулю достижимых сумм. Если при очередной вставке в дерево найдено точное совпадение нодов разного типа, то решение найдено.
Оставить комментарий
ceylor
задачка тут попалась, думаю как бы ее решить красиво, пока идей мало..суть есть ряд чисел, нужно найти любую комбинацию дающую заданную сумму
пусть чисел 250. сумма нужна 100000
все они вида 3000,07 2334,88 20000,90 и т.п.
заранее спасибо откликнувшимся