 |
eXeL@B —› Оффтоп —› Пытаюсь придумать алгоритм |
| Посл.ответ | Сообщение |
|
|
Создано: 26 октября 2012 17:24 · Личное сообщение · #1 Есть задача, для которой пытаюсь разработать алгоритм. Не могу найти красивое и простое решение. Вкратце расскажу, о чём речь. Устройство может принимать и отдавать купюры, до 80-ти штук распределяемые на N каналов у каждого из которых своя цена. Для примера возьмём 5 каналов с купюрами 5, 10, 20, 50, 100. Кол-во купюр на каждом из каналов от 0 до 80, но максимум 80 на все каналы. Количество постоянно меняется, то есть добавляются новые банкноты и мы можем выдавать сохранённые. Естественно, всегда знаем сколько у нас есть. Задача алгоритма сформировать максимально возможную сумму к выплате с учётом того, что с одной стороны желательно выдавать как можно меньше купюр, а с другой сохранять некий баланс, чтобы не оставалось каких-то одних много и подобными им не были заняты все 80 возможных позиций. Хотя тут можно сделать ограничение на канал, 15 или 20. Например, если у нас есть одна сотня и пять полтинников, а выдать нужно сто, то лучше если это будут две банкноты по 50. Но если у нас два полтинника и сотня – выдаём сотню. Я понимаю, что можно оптимизировать или по распределению банкнот, или по количеству ибо это два разных алгоритма и если нельзя выбрать что-то среднее, то лучше оптимизировать по кол-ву. То есть выдача с наименьшим кол-вом банкнот. Так же никогда нельзя предугадать какие банкноты будут приходить чаще или какие и когда потребуются выплаты. Задача пересчитывать из имеющегося, сколько максимально от запрошенной суммы может быть выдано. Минимум у нас это 5, если имеется хотя бы одна банкнота, иначе следующая по старшинству, максимум 2000, более не нужно. Как я подошёл к решению. Так как идей насчёт логики просчёта всего вышеописанного у меня нет, я выбрал самый глупый и ресурсоёмкий процесс которым всё-таки можно добиться результата. Я просчитал все варианты на 5 каналов по 25 банкнот максимум на каждом. 25*25*25*25*25 и выбрал из них все до 2000 включительно. У меня получилось 4,5 миллиона комбинаций. Без всякого сжатия это файл 22-23 мб, так же сделал индекс из 400 записей где каждая запись даёт прирост на 5. Следовательно, из этого индекса могу легко узнать, что комбинации для выплаты 280 у меня начинаются с 9556 записи в базе и заканчиваются 10203. Далее предполагается сделать так: 1) Пробежаться назад от записи 10203 к первой например и выбрать все записи где кол-во банкнот на канал не более чем есть у нас. 2) Узнать максимально приближённую сумму к желаемой и выбрать все записи с этой суммой. 3) Выбрать из этих записей ту, которая подходит нам более по минимальному количеству выдаваемых банкнот или по более менее равному распределению по каналам. Чем более думаю об этом, тем более глупым кажется моё решение. Очень нужны свежие идеи! p.s. Всё делаю на Delphi, под базой подразумеваю двоичный файл а не реальную базу данных… Спасибо если дочитали до конца!  |
|
|
Создано: 26 октября 2012 23:22 · Личное сообщение · #2 Это, похоже, задача о банкомате. Решаем методом динамического программирования, при появлении коллизий - выбором наименьшего колличества купюр. А базы и индексы - это, конечно, оригинально. ----- Stuck to the plan, always think that we would stand up, never ran. |
|
|
Создано: 27 октября 2012 15:37 · Личное сообщение · #3 Дочитал до конца  . Имхо можно пробывать решать как задачу оптимизации (целочисленного линейного программирования). Доводы в прицепе. 830c_27.10.2012_EXELAB.rU.tgz - Bankomat.rtf
----- 127.0.0.1, sweet 127.0.0.1 |
|
|
Создано: 27 октября 2012 20:31 · Личное сообщение · #4 OKOB пишет: Дочитал до конца . Имхо можно пробывать решать как задачу оптимизации (целочисленного линейного программирования). Доводы в прицепе. Я доводы тоже дочитал до конца, только это мне совсем не помогло...Видимо такие "оригинальные" идеи как базы и индексы рождаются у меня не спроста... Чего греха таить, я плохо учился в школе и было это очень давно. Из написанного я вообще ничего не понял. Сразу пошёл на вики, что бы прочитать о симплекс-методе, но запутался ещё больше. Говорили мне, что математика понадобится, а мне химия нравилась... Очень хорошо, что есть сервис где можно поиграться, но плохо то, что там на 10 переменных, а у нас их 11... Если мы возьмём не 5 каналов с банкнотами, а 4 или 3, то как можно подогнать всё написанное, что бы на том же онлайн сервисе по нажимать и понять, что вообще получается и как работает? ARCHANGEL пишет: Это, похоже, задача о банкомате. Решаем методом динамического программирования Точнее о железяке ITL NV200 SMART Payout, а применить можно где угодно. Буквально вчера появилась идея разбития задачи на подзадачи, теперь знаю, что правильно это называется методом динамического программирования. Хотя всё равно не уверен, что правильно понимаю... Нужно оба варианта попробовать, если осилю первый... |
|
|
Создано: 27 октября 2012 23:12 · Личное сообщение · #5 Появилась вот такая идея (наверное это ближе к методу динамического программирования). Сперва проверяем сколько у нас всего, и если менее того, что нужно выдать, то выдаем всё. Далее так как сумма может быть от 5 до 2000, кратная пяти, то сразу смотрим есть ли в конце пятёрка и готовим её на выдачу если она у нас имеется. Потом проверяем сколько у нас сотен. Их может быть от 0 до 20 и проверяем кол-во десятков в остатке, их соответственно от 0 до 9. Другими словами сумма 1275 это 5, 12 по 100 и 70. Так как ранее я делал базу вариантов, то мне оттуда пригодится всего 196 записей с выдачей 10, 20, 30, 40, 50, 60, 70, 80, 90, 100. Нужно только отсортировать варианты интеллектуально, например при наличии всего в достатке идеальный вариант для выдачи 90 это 50+2*20, если так нельзя, то 50+20+2*10, потом 50+4*10, 4*20+10, 3*20+3*10 и т.д. вплоть до пятёрок. Тут не суть важно как именно, главное добавить немного выборки, например для выдачи сотни лучше применить 1*100 чем 2*50, но если полтинников гораздо больше чем сотен или сотня последняя, можно выбирать второй вариант. Соответственно и далее, сравнивать кол-во купюр и отдавать предпочтение соседним меньшим, если крупных дефицит. Для суммы 1275 нужно вызвать эту "умную" функцию раз для 5, 12 раз для 100 и раз для 70 соответственно каждый раз передавая кол-во свободных купюр, получая сколько осталось после выдачи и добавляя к счётчикам на выдачу варианты после каждого захода в функцию... Последнее сложно получилось описать, но думаю понятно, что я имел ввиду... |
|
|
Создано: 28 октября 2012 00:32 · Поправил: OKOB · Личное сообщение · #6 Для 4х каналов, без купюр достоинством 5.  Для поиграть изменять значения в самом правом столбце (правая часть ограничений) и в функции цели (первые 4 коэффициента). Для ориентирования, на скрине заданы: формируемая сумма - 1000, возможно использовать 30 купюр достоинством 10, 25 купюр достоинством 20, 15 купюр достоинством 50 и 10 купюр достоинством 100. Симплекс-методом вообще не получилось (косяки ресурса??), Гомори в этой постановке посчитал, но в результате выгреб все купюры младшего достоинства с большими весовыми коэффициентами набрав сумму 74 купюрами, что свидетельствует о недостатке целевой функции. Сейчас в качестве весовых коэффициентов используются значения ресурса купюр. Можно отвязаться в них от ресурсов и использовать какие либо импирические значения. ----- 127.0.0.1, sweet 127.0.0.1 |
|
eXeL@B —› Оффтоп —› Пытаюсь придумать алгоритм |
Для печати