Выбрать дату в календареВыбрать дату в календаре

Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 124 След.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Сделал немного другую реализацию на VBA поиска слагаемых, когда есть суммы и кол-ва
может кому нибудь пригодится
Считает на VBA по сравнению с C++ значительно медленнее
Комбинаторика. Раскрой арматуры, Как оптимально разрезать хлысты арматуры заданного размера на заданное количество кусков заданной длины
 
Цитата
Adamm написал:
но хотелось бы решение в экселе
Есть реализация в Excel (демо-версия полностью функциональна): http://www.excelworld.ru/forum/3-21304-1
Результат работы во вложении
Изменено: MCH - 19.04.2021 14:41:05 (исправлена ссылка)
Подбор оптимального количества книг (по толщине) для размещения в посылке заданной высоты
 
решение Жадиной
Подбор оптимального количества книг (по толщине) для размещения в посылке заданной высоты
 
Цитата
Xel написал:
по-моему, это крутая математика, там и макрос был бы ой и вряд ли бесплатно.
По описанию, задача похожа на задачу линейного раскроя/упаковки в контейнеры
алгоритмы можно применять теже, можно найти и бесплатные реализации: http://www.excelworld.ru/forum/3-21304-1

А формулами можно реализовать "жадный" алгоритм
Изменено: MCH - 19.01.2021 16:57:54
Алгоритмы. Игры. Сортировка объектов по контейнерам
 
Какие ограничения в игре?
Чему равно N? сколько всего колб максимально? сколько различных цветов?
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Все таки C++ обгоняет FB, если в 32bit это не так заметно, то в 64bit разница ярко выражена, может быть разница в компиляторах и оптимизации кода
Разбить число на количество единиц.
 
Код
=ЛЕВСИМВ(ПОВТОР("1;";A1);A1*2-1)

Код
=ПОВТОР("1;";A1-1)&1
Изменено: MCH - 24.12.2020 14:26:07
Количество контейнеров каждого типа для размещения набора деталей
 
Рабочая демоверсия есть здесь: http://www.excelworld.ru/forum/3-21304-1
Количество контейнеров каждого типа для размещения набора деталей
 
Одно из решений
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Интересен результат.
XLL 32бит - 9,9 сек
XLL 64бит - не запускается т.к. система 64, Excel 32
FB 32 бит - 10,5 сек 8,9 сек
FB 64 бит - 4,9 сек 3,9 сек

Виталий, протестируй код на FreeBasic на своем компьютере, сопоставима будет скорость с C++? Я немного скорректировал код.
Изменено: MCH - 12.12.2020 09:42:40
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Вариант на FreeBasic
Все данные находятся в txt файле, после решения результат сохраняется также в txt
У меня версия 64бит считает 5 секунд 3-4 сек
XLL не тестировал, не разобрался еще как это сделать

UPD: файл обновил
Изменено: MCH - 12.12.2020 09:39:17
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
На тестовом стенде (ранее выложенный файл) - 2 сек
У меня FreeBasic считает значительно дольше 2х секунд
Выложить реализацию на FreeBasic в 1 поток для теста?
Изменено: MCH - 11.12.2020 16:13:13
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Пока с потоками не получается сделать, видимо сама концепция разделения на параллельные вычисления не правильная, подумаю еще
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Михаил, что быстрее стек или предыдущее изменения?
У меня получается стек немного быстрее и он не требует сокращения на НОД, но нужно выделять больше памяти

Цитата
bedvit написал:
Я так понимаю со стеком  - это под вопросом (важна очередность)?
Стек разделять на потоки наверное сложнее, т.к. потоки должны работать с одним и тем же стеком, будут конфликты между потоками

Цитата
bedvit написал:
На freebasic не получилось с потоками сделать? у меня здесь вопросы есть.
Пока нет времени, может вечером получится набросать

Хочу немного изменить ввод и вывод данных
на входе размер слагаемого и кол-во (по умолчанию кол-во = 1)
на выходе порядковый номер слагаемого и их кол-во, можно выводит как в сжатом виде так и полный перечень всех слагаемых с нулевым количеством (если слагаемое не используется)
Это пригодится например в задаче раскроя
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Пока не пойму куда это нужно добавить.
Решение через очередь/стек - небольшой прирост производительности на поиске больших сумм

UPD: При использовании очереди уже нет такой острой необходимости по сокращению значений на НОД, исключительно только для сокращения выделяемой памяти, на скорость решения не должно сильно влиять.
Изменено: MCH - 10.12.2020 15:38:57
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
не взлетает, наверное  есть и другие зависимопотоковые данные, например переменная "К"?
ну k в каждом потоке должна быть локальной, а при нахождении решения присваиваем ее значение глобальной переменной
Попробую на freebasic сделать с потоками
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Виталий, внеси небольшие правки в код на VBA, ну и на C++
см. строки 41-46 и 51
Скрытый текст

Сокращение времени расчета при поиске суммы близкой к сумме всех слагаемых более чем в 1,5 раза

А еще можно что то типа очереди или стека придумать (добавив еще один массив) и тогда должно еще быстрее считать, т.к. будут пропускаться часть операций по проверке массива
Изменено: MCH - 10.12.2020 14:11:16
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Идеи для ускорения алгоритма поиска слагаемых:
1. Думаю, что алгоритм легко разбить на потоки, в каждом потоке делаем цикл по слагаемым:
Код
For i = НомерПотока To n Step Кол-воПотоков

массивы arr(), arrIndex() - глобальные
При нахождения результата в одном из потоков заканчиваем расчеты по флагу во всех других потоках
Соответственно нужно разграничить одновременный доступ к глобальному массиву arrIndex()

2. Разбить алгоритм поиска слагаемых на два алгоритма:
Тот что есть - поиск слагаемых для суммы не превышающих исходную
и другой - поиск слагаемых не менее искомой суммы
В данном случае если искомая сумма больше половины суммы всех слагаемых, то лучше найти те числа, который нужно исключить из общего списка, это может дать значительное ускорение при поиске больших сумм (существенно больших половины суммы всех слагаемых).
Изменено: MCH - 10.12.2020 09:47:46
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Какие ограничения у этих двух алгоритмов? Что целесообразнее?
Если искомая сумма мала - до 10 000 (или до 1 млн) то динамическое программирование будет быстро находить решение при большом количестве слагаемых.
Если слагаемых несколько десятков и сумма может быть найдена в пределах десятка слагаемых - то перебором с МВиГ (метод ветвей и границ)

Предпочтительно начинать с динамического программирования, если искомая сумма большая, то пытаемся перебором, но ограничиваем решение по времени с выводом наилучшего найденного результата.
Либо эвристические алгоритмы типа "жадного" с различными его вариациями, с добавлением переборов.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Сам алгоритм суммы подмножеств/рюкзака динамическим программированием основан на создании массива размерностью равной искомой сумме и его перебору по всем слагаемым, отсюда и ограничения: целочисленность данных и ограничение в размере искомой суммы (ограничено возможной выделяемой памятью).
Если решать грубой силой (переборами), то разницы нет, целые числа или дробные, большие или маленькие, ограничение в решении связано с вариативностью и нехваткой времени на перебор всех вариантов.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Для чего функция "GCD"? Почему бы просто не умножить на 100, зачем НОД, в чем профит такого действия?
функция GCD  это и есть НОД алгоритмом Евклида

Сложность алгоритма нахождения слагаемых под нужную сумму динамическим программированием - N*M, где N -кол-во слагаемых, M - искомая сумма, и памяти выделяем M
Если все числа умножить на 100, то мы сразу замедляем алгоритм в 100 раз, поэтому, если все полученные числа кратны какому нибудь числу (2, 5, 10, 100 и т.п.), то нужно сократить их на наибольший общий делитель, тем самым в ряде случаев может получится более быстрое решение.
Так для целых чисел, после умножения их на 100, обратно сокращаем на те же 100, и скорость решения остается без изменения
Изменено: MCH - 08.12.2020 13:30:45
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Немного доработал макрос поиска слагаемых:
Может работать с копейками, все числа умножаются на 100 и округляется до целых чисел
Для ускорения работы затем все числа делятся на НОД (наибольший общий делитель)

На VBA большие числа уже заметно долго считает
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Цитата
bedvit написал:
Алгоритм явно неправильно отрабатывает. Ищу сумму "53263", а получаю "50653"
Сделал свою функция поиска слагаемых
на вход даем массив слагаемых, а также минимальную и максимальную требуемую сумму, на выходе формирует массив индексов слагаемых, и возвращает полученную сумму
Если удается найти сумму от МИН до МАКС, то возвращает первую найденную сумму из диапазона, если не удается найти - то ближайший найденный результат.
Изменено: MCH - 07.12.2020 15:36:07
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Задача по генерации оптимальных схем раскроя
Здесь и подбор слагаемых и перебор и ограничение ненужных вариантов. При этом кода не очень много
Для ускорения отключил вывод результата на лист, оставил только генерацию и подсчет количества вариантов

Например, со всеми простыми тестами VBA справляется достаточно хорошо, кроме последнего, где генерируется более 5 млн вариантов и времени требуется значительно больше.
Можно конечно перенести во FreeBasic, считать будет не намного медленнее, чем С++, но преимущество XLL подкупает.

Если получится максимально перенести вычислительные процессы в XLL, то можно реализовать достаточно быстрый алгоритм раскроя, а Excel будет только оболочкой для ввода/вывода информации.
Решения задач комбинаторики. XLAM or XLL (VBA or C++)
 
Виталий, привет.
О каких задачах комбинаторики речь?
Будут ли задействованы потоки при решении задач, нужно ли прописывать потоки алгоритмически или можно использовать встроенные оптимизаторы?

Мне интересно переложить на C++ и прикрутить решение к VBA:
Задачу линейного раскроя, алгоритмы перебора и линейное программирование
Задачу коммивояжера, особенно интересует как прикрутить k-opt оптимизацию, или LKH алгоритм
Реализовать Алгоритм Дейкстры (или другой алгоритм для нахождения кратчайших путей в графе), на сколько будет быстрее решать

Все реализации на VBA у меня есть

На форуме были задачки по кластеризации (k-means), Было бы интересно посмотреть скорость решения через XLL.

Из простого, можно начать с: сочетания, перестановки, размещения
Изменено: MCH - 04.12.2020 16:43:47
Рассчитать усреднение по курсу валют
 
Цитата
Ирина Тихонова написал:
как посчитать средний курс с 20 числа предыдущего месяца по 19 число настоящего?
Можно использовать две методологии:
1. Брать средние значения фактически устанавливаемых курсов по торгам, публикуемые на cbr.ru, при этом среднее берется не за 30/31 день, а меньше, т.к. курс на воскресение и понедельники не устанавливается (т.к. нет торгов на бирже)
2. Брать среднее значение всех курсов, действующие на каждую дату (даже если нет торгов)

Пример во вложении.
На работе применяется вариант 1, для формульного ценообразования на сырье.
Изменено: MCH - 30.11.2020 13:55:28
Разнесение и подсчёт количества серий из цифр в строке, количества цифр и их сумм в заданном диапазоне
 
Цитата
Peet написал:
т.е. если в строке идёт 24245 6 7 24 - то 1 серия сумма 53 и 3 числа сумма 47
у меня получается 6 + 7 + 24 = 37, а не 47

В принципе, моя функция так и считает
Изменено: MCH - 24.11.2020 17:15:46
Разнесение и подсчёт количества серий из цифр в строке, количества цифр и их сумм в заданном диапазоне
 
Реализовал как понял:
Если подряд сумма часов превышает 24, то считаем ее как вариант 1, если не превышает, то как вариант2
поэтому подряд 2+2 или 3+3 это одна серия, но суммарно менее 24, возможно нужно как то иначе реализовать
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
только так не лучше?
Можно еще на пару символов сократить:
Код
=МАКС(МУМНОЖ(ЕСЛИОШИБКА(ПОИСК(C$1;{0;""}&$B2;СТРОКА($2:$99)););{-1:1}))
Максимальные расстояния между одинаковыми знаками строки
 
Цитата
БМВ написал:
только так не лучше?
Наверно лучше, немного не дожал
Страницы: 1 2 3 4 5 6 7 8 9 10 11 ... 124 След.
Наверх