:: Игры Разума
Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
Задача такова:

Есть массив чисел. Задается A и B. Нужно найти A чисел из массива, сума которых максимально приближается к B.

Я так понимаю я хожу по массиву и циклом суммирую до посинения сравнивая результати. А есть ли какой-то хитроумный алгоритм на эту тему?
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
travelFox
Задача такова:
Есть массив чисел. Задается A и B. Нужно найти A чисел из массива, сума которых максимально приближается к B.

Я так понимаю я хожу по массиву и циклом суммирую до посинения сравнивая результати. А есть ли какой-то хитроумный алгоритм на эту тему?
есть ли отрицаетльные чсила?
целые ли числа?
приближается (больш-меньш) или тока (меньш)?
а кроме того - монаж и в курсоры массив преобразовать - и нехай СКЛ шпарит поиск


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина




Исправлено 2 раз(а). Последнее : Mitchman, 19.10.11 10:45
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Владимир Максимов

Сообщений: 14095
Откуда: Москва
Дата регистрации: 02.09.2000
Не совсем то, но достаточно близко

подбор слагаемых для поиска суммы
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
может ты просто решаешь класическую задачу о загрузке рюкзака?


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
Спасибо за подсказки. Вникаю.
А что такое СКЛ?



Исправлено 1 раз(а). Последнее : travelFox, 19.10.11 10:59
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
если таки о рюкзаке то вот
ru.wikipedia.org/wiki/Задача_о_ранце

СКЛ - SQL


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина




Исправлено 2 раз(а). Последнее : Mitchman, 19.10.11 11:00
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
А ШО? SQL имеет готовую реализованую функцию для этого?
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
travelFox
А ШО? SQL имеет готовую реализованую функцию для этого?
нет но поиск в в нем работает лучше

------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
так я не услышал ответы на вопросы?
дело таки в ранце?
комбинаторика?


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
Mitchman
так я не услышал ответы на вопросы?
дело таки в ранце?
комбинаторика?

Не совсем. В ранце более одного условия. У меня прото "набрать товара на сумму не более/равно"
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
travelFox
Mitchman
так я не услышал ответы на вопросы?
дело таки в ранце?
комбинаторика?

Не совсем. В ранце более одного условия. У меня прото "набрать товара на сумму не более/равно"
схема решения та же


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Как я понимаю, мы получим (N*N+N)/2 сочетаний, где N - количество элементов.
Распределив весовые коэффициенты, (стоимости), можно потом результат отсортировать и найти максимальное приближение к заданной величине.

Хотя, не так, если подумать.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.




Исправлено 2 раз(а). Последнее : Влад Колосов, 19.10.11 15:39
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Массив - константа? Если да, и позволяют размеры массива, то можно заранее составить N табличек
(где N - размерность массива), которые содержат все возможные комбинации элементов (с учетом порядка элементов), и отсортировать эти таблицы по сумме элементов.
Впрочем, если размер массива не позволяет, то и прямое решение с помощью перебора малореально, как и в задаче об укладке ранца.



Исправлено 1 раз(а). Последнее : medstrax, 19.10.11 18:51
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Я правильно понимаю, что задаётся ТОЧНОЕ число выбираемых элементов? Т.е. из массива в N элементов выбирается РОВНО A штук? Просто "классическая" задача (Subset sum problem) формулируется как выбор произвольного числа элементов с ТОЧНОЙ заданной суммой, и как подвариант - выбор с суммой находящейся "близко" к заданной сумме - при том последний вариант имеет весьма эффективное решение (конечно же не требующее полного перебора, т.к. это НАИМЕНЕЕ эффективное решение - по сути это максимальная сложность/время), в отличие от "чистой" классической задачи.
При том повторно выбирать один и тот-же элемент нельзя (хотя в массиве могут находится и одинаковые числа)? При том "максимально приближается" - это значит просто минимизацию разницы между набранной суммой и B (при том набранная сумма может быть и больше и меньше чем B, и при том может СУЩЕСТВЕННО отличаться от B по величине) или же предполагается условие, что сумма, помимо всего прочего, <= B?
Так же крайне желательно указать предполагаемые значения N, A, B, Max(Ci)... Т.к. некоторые алгоритмы сразу отпадают по таким ограничениям


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
Я уже бьюсь с этой задачкой просто сил нет.
Количество элементов на входе константа А.
Необходимо отобрать из массива из А элементов, "любое" количество элементов сумма которых не превысит B (будет равно B или максимально приблизится к B).



Исправлено 2 раз(а). Последнее : travelFox, 19.10.11 22:22
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
Select TOP 1 t1.Id Id1,t2.ID Id2,t3.ID Id3,t4.ID Id4,
t1.Sum Sum1,t2.Sum Sum2,t3.Sum Sum3,t4.Sum Sum4,
T1.Sum+t2.Sum+t3.Sum+t4.Sum AllSum
From ((MyTab T1 JOIN MyTab T2 ON T1.ID<T2.ID)
JOIN MyTab T3 ON T3.ID>t2.ID)
JOIN MyTab T4 ON T4.ID>t3.ID
WHERE T1.Sum+t2.Sum+t3.Sum+t4.Sum<=m.SumB
ORDER BY 9 DESC
ну это при ограниченном количестве A я взял А=4


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина




Исправлено 4 раз(а). Последнее : Mitchman, 19.10.11 23:11
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
Если же их любое количество - тоди методом Рюкзака
алгоритм оч хорошо описан по ссылкам выше


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
matod

Сообщений: 3062
Откуда: Иркутск
Дата регистрации: 31.10.2001
Мне кажется, что задача по прежнему сформулирована недостаточно четко. Отсюда и сложности в ее решении. "Набрать товара на сумму не более В" можно по разному. Например, если каждый товар можно выбирать несколько раз, т.е. например на 10 руб можно предложить 10 коробков спичек по рублю. Можно ли "дробить" товар - он непрерывный или дискретный, т.е. например взять 300 грамм соли на сумму 9.99 руб.
В зависимости от этого это может быть действительно вариант задачи о рюкзаке, а может лучше подойдут методы линейного программирования, в частности задача с целочисленными решениями для дискретного товара. Там можно задавать ограничения на доступное количество товара, например. Или иные ограничения, которые можно выразить в виде линейных форм.
Либо, как заметил Игорь, это "задача о суммах подмножеств" или какая-то другая из комбинаторики или динамического программирования...

Каждый из этих вариантов довольно хорошо исследован и несложно найти нужную информацию, вплоть до готовых алгоритмов. Главное - правильно поставить вопрос, учитывая всевозможные ньюансы. Так, если товаров очень много, а сумма велика, то поиск оптимального решения может оказаться довольно долгим и тогда может быть окажется полезным искать не оптимальное решение, а "достаточно хорошее". Одно дело, когда товаров всегда больше, чем покупатель может купить, и совсем другое - когда в наличии ограниченное кол-во... и т.д.
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
В таком случае это вариант en.wikipedia.org - при том если все элементы неотрицательные, то там же описан алгоритм нахождения решения "приближенного к B" (Polynomial time approximate algorithm) - к сожалению статья не переведена, но думаю понять что там к чему несложно...
При большом желании можно запускать алгоритм несколько раз, меняя параметр "близости суммы набора к заданному числу". Естественно, это НЕ будет оптимальное решение (разве что параметр c подобрать так, чтобы в "зазор" попадало не более чем 1 возможное решение - но это приведёт к перебору практически всех вариантов, что есть весьма неоптимально), но оно будет приближено к нему настолько, насколько тебе это необходимо.

Задача о рюкзаке есть БОЛЕЕ общая задача, чем задача о сумме подмножества (она по сути сводится, конечно, если брать "вещи" с совпадающей "стоимостью" и "весом"), потому не думаю что стоит себе усложнять жизнь решая более общую задачу, если тут достаточно решить более "частную".
Перебор практически не годится для случаев A > 30, да и для A порядка 20 это уже будет крайне медленно (число возможных выборок составляет 2^A).

Вообще, если это практическая задача (ну там отгрузка/разрезка листопроката/металлолома), то лучше было бы уточнить "физический смысл" - от этого ведь зависят многие "допущения" при выборе алгоритма...


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата регистрации: 22.02.2011
Ну хорошо. Давайте с малого. Имея x1,x2,x3,x4 как циклом сделать обход 2^4 функций?:

x1+x2+x3+x4
x1+x2+x4
x1+x2+x3
x1+x3+x4
x2+x3+x4
x1+x2
x2+x3
x2+x4
x3+x1
x3+x4
x4+x1
...
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 4 (Гостей: 4)

© 2000-2024 Fox Club 
Яндекс.Метрика