Guest
Новичок
|
    
Дано: Есть одномерный массив положительных чисел.
есть положительное число Z, которое обычно лежит в интервале равном сумме нескольких элементов массива.
собственно нужен алгоритм нахождения ОПТИМАЛЬНОЙ суммы неких элеменотов массива, чья бы сумма была как можно более близка по значению к заданному числу Z.
хочется быстрый и оптимальный алгоритм.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 13 нояб. 2005 11:21 | IP
|
|
KMA 
Долгожитель
|
 
УУУУ... Быстрый и оптимальный. Надо подумать. У тебя самого какие идеи есть. Как неоптимальный найти это понятно, но даже оптимальный найти тоже не проблема, но как сделать его быстрым? Тебе сойдет поиск оптимальной суммы неоптимальным кодом? 
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 17 дек. 2005 22:29 | IP
|
|
KMA
Долгожитель
|
Есть идея...
Значит создаем массив из положительных чисел, задаем Z.
Сортируем этот массив по возрастанию.
Сравниваем последнее значение с Z.
Если больше, то сравниваем предпоследнее.
Если на немного меньше, то прибавляем первое и сравниваем или в несколько раз меньше, то прибавляем предпоследнее, опять сравниваем.
Если даже и близко не стояло, значит второе, если и это близко то третье, когда-нибудь да перевалит, тогда ты сравниваешь перевалившее значение со значением недобора, а это предпоследнее число перед числом, давшим перевал, и смотришь разницу между ними.
Т. е. таким образом на первом шаге ты ищешь элементы, которые максимально приближают Z к реальному значению и так как ты ишишь среди максимальных чисел, то сумма, приближающая будет минимальной.
Второй шаг отслеживаешь числа с минимальными значениями и смотришь уже их. Вот, вроде со стороны математики все верно, нам ведь в первую очередь оптимальную сумму, а уже потом, среди этой оптимальной суммы искать приближенное, ведь я так понял.
Напишешь я думаю сам, здесь думать особо много не надо, надо лишь примерно оценить где во много раз болше, а где на небольшую величину. Ну и там соответственно посмотреть, где последнее большое, с числом рядом стоящим с этим последним большим. Вот...
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 17 дек. 2005 23:00 | IP
|
|
Dzen
Удален
|
Ничего не понял.
Если на немного меньше, то прибавляем первое и сравниваем или в несколько раз меньше, то прибавляем предпоследнее, опять сравниваем.
Пожалуйста расшифруй это предложение.
Ну и там соответственно посмотреть, где последнее большое, с числом рядом стоящим с этим последним большим.
Ааааа??? (Испуганно)
здесь думать особо много не надо
Заметно.
P.S.Извини не хотел тебя обидеть, просто действительно ничего не понятно. А этой задачей я интересуюсь уже давно, вот только пока не придумал алгоритм(ну кроме брутал форса)
который бы гарантированно находил оптимальную сумму. Если твой алгоритм действительно работает... То просто класс. 
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 18 дек. 2005 22:22 | IP
|
|
Guest
Новичок
|
Насколько я знаю, это NP-полная задача.
Поэтому _самый_ оптимальный ответ может быть гарантировано получен только перебором. Все остальные методы не гаранитуют 100%-й оптимальности, но вполне работоспособны. В данной задаче хорошо то, что точно известен и легко вычисляем критерий оптимальности: остаток равен =0.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 19 дек. 2005 12:52 | IP
|
|
KMA
Долгожитель
|
Расшифровываю фразы. Немного меньше, значит не больше следующего максимального элемента.
Т. е. есть оцениваем s> a[n], то число на много больше и можно вычитаем следующий элемет массива с конца s:=s-a[n], далее сравниваем уже с меньшим элементом, т. е. s>a[n-1] , если да, то вычитаем s:=s-a[n-1] и т. д., когда нибудь да не выполниться условие s> a[n-m], тогда начинаем потихоньку просматривать первые элементы массива, если же вычет первого элемента уже из известного s дает отрицательное значение, то надо посмотреть является ли это значение большим при условии, что s:=s-s[n-m-1], какое число будет больше, то и победит. Ну и аналогично этой ситуации рассматриваем первые элементы.
Но я не хочу сказать, что мой алгоритм есть круто, просто это идея\совет, а их как гласит послоница надо обдумывать.
Dzen я и не обиделся совсем, понимаю, что моя речь желает оставлять только лучшее.
|
Всего сообщений: 940 | Присоединился: декабрь 2005 | Отправлено: 19 дек. 2005 15:13 | IP
|
|
Guest
Новичок
|
Псевдополиномиальные алгоритмы - внешняя ссылка удалена
___________________________________
Такие алгоритмы часто получаются при применении динамического программирования к NP-полным задачам. У таких алгоритмов экспоненциальная зависимость времени работы (и памяти компьютера) от длины входа, однако существует полиномиальная зависимость от некоторого числа (чисел) на входе задачи. Такие алгоритмы очень полезны, т. к. позволяют точно решать задачи с маленькими числами и приближенно — для больших чисел, каким-либо образом преобразованных в маленькие.
Пример 1. Задача о суммах подмножеств ("табличный" алгоритм)
Пусть задана пара (S, t), где S = {x1, x2, …, xn} представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S, сумма которых не превосходит t, такое, у которого сумма ближе всего к t.
Пусть |S| = n. Обозначим (k, w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w. Таким образом исходная задача — это задача (n, t).
Для решения задачи построим таблицу T[n, t + 1], в клетку T[i, j] которой будем записывать оптимальное решение задачи (i, j).
Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x1) — числами x1. Клетку T[i, j] (i, j > 1) будем заполнять по правилу:
Если j − xi > 0, то y := T[i − 1, j − xi], иначе y := 0;
T[i, j] := max(T [i − 1, j], y + xi)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
3 0 0 0 3 3 3 3 3 3 3 3 3 3 3
5 0 0 0 3 3 5 5 5 8 8 8 8 8 8
7 0 0 0 3 3 5 5 7 8 8 10 10 12 12
9 0 0 0 3 3 5 5 7 8 9 10 10 12 12
11 0 0 0 3 3 5 5 7 8 9 10 11 12 12
S = {3, 5, 7, 9, 11} t = 13;
Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12.
Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования xi (T[i − 1, j]), либо если xi входит в сумму (y + xi). В этом случае его надо прибавить к решению задачи (i − 1, j − xi), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы.
Трудоемкость этого алгоритма составляет O(nt) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 13 июня 2008 13:23 | IP
|
|
|
Форум
Нужен алгоритм нахождения опт. суммы
