Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Задача такова:
Есть массив чисел. Задается A и B. Нужно найти A чисел из массива, сума которых максимально приближается к B. Я так понимаю я хожу по массиву и циклом суммирую до посинения сравнивая результати. А есть ли какой-то хитроумный алгоритм на эту тему? |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
есть ли отрицаетльные чсила? целые ли числа? приближается (больш-меньш) или тока (меньш)? а кроме того - монаж и в курсоры массив преобразовать - и нехай СКЛ шпарит поиск ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина Исправлено 2 раз(а). Последнее : Mitchman, 19.10.11 10:45 |
Re: Можно ли оптимизировать? | |
---|---|
Владимир Максимов Сообщений: 14100 Откуда: Москва Дата регистрации: 02.09.2000 |
|
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
может ты просто решаешь класическую задачу о загрузке рюкзака?
------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Спасибо за подсказки. Вникаю.
А что такое СКЛ? Исправлено 1 раз(а). Последнее : travelFox, 19.10.11 10:59 |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
если таки о рюкзаке то вот
ru.wikipedia.org/wiki/Задача_о_ранце СКЛ - SQL ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина Исправлено 2 раз(а). Последнее : Mitchman, 19.10.11 11:00 |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
А ШО? SQL имеет готовую реализованую функцию для этого?
|
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
нет но поиск в в нем работает лучше ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
так я не услышал ответы на вопросы?
дело таки в ранце? комбинаторика? ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Не совсем. В ранце более одного условия. У меня прото "набрать товара на сумму не более/равно" |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
схема решения та же ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Можно ли оптимизировать? | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Как я понимаю, мы получим (N*N+N)/2 сочетаний, где N - количество элементов.
Распределив весовые коэффициенты, (стоимости), можно потом результат отсортировать и найти максимальное приближение к заданной величине. Хотя, не так, если подумать. ------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. Исправлено 2 раз(а). Последнее : Влад Колосов, 19.10.11 15:39 |
Re: Можно ли оптимизировать? | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Массив - константа? Если да, и позволяют размеры массива, то можно заранее составить N табличек
(где N - размерность массива), которые содержат все возможные комбинации элементов (с учетом порядка элементов), и отсортировать эти таблицы по сумме элементов. Впрочем, если размер массива не позволяет, то и прямое решение с помощью перебора малореально, как и в задаче об укладке ранца. Исправлено 1 раз(а). Последнее : medstrax, 19.10.11 18:51 |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Я правильно понимаю, что задаётся ТОЧНОЕ число выбираемых элементов? Т.е. из массива в N элементов выбирается РОВНО A штук? Просто "классическая" задача (Subset sum problem) формулируется как выбор произвольного числа элементов с ТОЧНОЙ заданной суммой, и как подвариант - выбор с суммой находящейся "близко" к заданной сумме - при том последний вариант имеет весьма эффективное решение (конечно же не требующее полного перебора, т.к. это НАИМЕНЕЕ эффективное решение - по сути это максимальная сложность/время), в отличие от "чистой" классической задачи.
При том повторно выбирать один и тот-же элемент нельзя (хотя в массиве могут находится и одинаковые числа)? При том "максимально приближается" - это значит просто минимизацию разницы между набранной суммой и B (при том набранная сумма может быть и больше и меньше чем B, и при том может СУЩЕСТВЕННО отличаться от B по величине) или же предполагается условие, что сумма, помимо всего прочего, <= B? Так же крайне желательно указать предполагаемые значения N, A, B, Max(Ci)... Т.к. некоторые алгоритмы сразу отпадают по таким ограничениям ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Я уже бьюсь с этой задачкой просто сил нет.
Количество элементов на входе константа А. Необходимо отобрать из массива из А элементов, "любое" количество элементов сумма которых не превысит B (будет равно B или максимально приблизится к B). Исправлено 2 раз(а). Последнее : travelFox, 19.10.11 22:22 |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина Исправлено 4 раз(а). Последнее : Mitchman, 19.10.11 23:11 |
Re: Можно ли оптимизировать? | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
Если же их любое количество - тоди методом Рюкзака
алгоритм оч хорошо описан по ссылкам выше ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
Re: Можно ли оптимизировать? | |
---|---|
matod Сообщений: 3062 Откуда: Иркутск Дата регистрации: 31.10.2001 |
Мне кажется, что задача по прежнему сформулирована недостаточно четко. Отсюда и сложности в ее решении. "Набрать товара на сумму не более В" можно по разному. Например, если каждый товар можно выбирать несколько раз, т.е. например на 10 руб можно предложить 10 коробков спичек по рублю. Можно ли "дробить" товар - он непрерывный или дискретный, т.е. например взять 300 грамм соли на сумму 9.99 руб.
В зависимости от этого это может быть действительно вариант задачи о рюкзаке, а может лучше подойдут методы линейного программирования, в частности задача с целочисленными решениями для дискретного товара. Там можно задавать ограничения на доступное количество товара, например. Или иные ограничения, которые можно выразить в виде линейных форм. Либо, как заметил Игорь, это "задача о суммах подмножеств" или какая-то другая из комбинаторики или динамического программирования... Каждый из этих вариантов довольно хорошо исследован и несложно найти нужную информацию, вплоть до готовых алгоритмов. Главное - правильно поставить вопрос, учитывая всевозможные ньюансы. Так, если товаров очень много, а сумма велика, то поиск оптимального решения может оказаться довольно долгим и тогда может быть окажется полезным искать не оптимальное решение, а "достаточно хорошее". Одно дело, когда товаров всегда больше, чем покупатель может купить, и совсем другое - когда в наличии ограниченное кол-во... и т.д. |
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 |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Ну хорошо. Давайте с малого. Имея x1,x2,x3,x4 как циклом сделать обход 2^4 функций?:
|
© 2000-2024 Fox Club  |