Строительство, ремонт, обустройство дачного участка Советы и рекомендации про строительство дома и ремонт своими руками. Интересные идеи для обустройства загородного дома и дачного участка!
Калькулятор решает задачу об упаковке в контейнеры разными эвристическими алгоритмами. Создано по запросу пользователя.
Тут давеча пользователь Artuem оставил очень интересный запрос — Калькулятор количества целых досок из отрезков.
Приведу его здесь полностью, чтобы не прерывать нить повествования: «Есть некоторое количество отрезков разной длины, необходимо рассчитать минимальное кол-во досок из которых их можно нарезать, или что то типа того :)»
Немного подумав, можно понять, что сие есть не что иное, как формулировка Задачи об упаковке в контейнеры.
Иными словами, имеются контейнеры фиксированного объема и набор предметов произвольного объема (понятно, что объем каждого предмета в отдельности меньше объема контейнера). Требуется упаковать эти предметы в минимальное число контейнеров.
Можно еще привести пример «из жизни» — есть набор файлов (например, кинофильмы) разного размера. Требуется записать весь набор на наименьшее число DVD-дисков. Ну и так далее. Частным случаем этой задачи является задача о рюкзаке, кстати.
Задача эта — NP-полная, то есть для гарантированного нахождения оптимального решения нужен полный перебор. Однако есть эвристические алгоритмы для нахождения подходящего решения. Если повезет, оно будет и оптимальным 🙂
Ниже калькулятор, а используемые алгоритмы, как водится, описаны под ним. И кстати, хоть на данных по умолчанию некоторые решения совпадают, но алгоритмы все-таки разные, и на других данных различия будут заметны.
