for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата: 19.10.11 08:26:13ОтветитьЦитировать
Задача такова:

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

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

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 09:41:55ОтветитьЦитировать
travelFox
Задача такова:
Есть массив чисел. Задается A и B. Нужно найти A чисел из массива, сума которых максимально приближается к B.

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


------------------
а будни - это попросту антракт




Исправлено: Mitchman, 19.10.11 09:45
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Владимир Максимов

Сообщений: 13839
Откуда: Москва
Дата: 19.10.11 09:48:39ОтветитьЦитировать
Не совсем то, но достаточно близко

подбор слагаемых для поиска суммы
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 09:48:44ОтветитьЦитировать
может ты просто решаешь класическую задачу о загрузке рюкзака?


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
travelFox
Автор

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



Исправлено: travelFox, 19.10.11 09:59
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 09:59:12ОтветитьЦитировать
если таки о рюкзаке то вот
ru.wikipedia.org/wiki/Задача_о_ранце

СКЛ - SQL


------------------
а будни - это попросту антракт




Исправлено: Mitchman, 19.10.11 10:00
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
travelFox
Автор

Сообщений: 344
Откуда: Червоноград
Дата: 19.10.11 10:44:13ОтветитьЦитировать
А ШО? SQL имеет готовую реализованую функцию для этого?
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

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

------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 11:01:10ОтветитьЦитировать
так я не услышал ответы на вопросы?
дело таки в ранце?
комбинаторика?


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
travelFox
Автор

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

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

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 11:10:24ОтветитьЦитировать
travelFox
Mitchman
так я не услышал ответы на вопросы?
дело таки в ранце?
комбинаторика?

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


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Влад Колосов

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

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


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




Исправлено: Влад Колосов, 19.10.11 14:39
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
medstrax

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



Исправлено: medstrax, 19.10.11 17:51
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Igor Korolyov

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


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
travelFox
Автор

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



Исправлено: travelFox, 19.10.11 21:22
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 22:03:10ОтветитьЦитировать
  
  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


------------------
а будни - это попросту антракт




Исправлено: Mitchman, 19.10.11 22:11
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
Mitchman
[Модератор]

Сообщений: 9469
Откуда: Николаев
Дата: 19.10.11 22:11:00ОтветитьЦитировать
Если же их любое количество - тоди методом Рюкзака
алгоритм оч хорошо описан по ссылкам выше


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Можно ли оптимизировать?
matod

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

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

Re: Можно ли оптимизировать?
Igor Korolyov

Сообщений: 32363
Дата: 20.10.11 16:31:29ОтветитьЦитировать
В таком случае это вариант 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
Откуда: Червоноград
Дата: 20.10.11 19:19:21ОтветитьЦитировать
Ну хорошо. Давайте с малого. Имея 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: 40 of63 avantum  and Guests: 38


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