Раньше я работал над программным обеспечением для изготовления изделий из дерева, стекла, камня и т. Д. И предоставлял средства для автоматической разметки деталей, минимизируя отходы.Многие из вас знают это как проблему с упаковкой мусорного ведра.Я наткнулся на это - http://www.dropbox.com/jobs/challenges#packing-your-dropbox - и обнаружил, что проблема интересна.
Дисковое пространство обычно рассматривается как одномерный массив, а файлы разбиваются на части, чтобы поместиться между ними.Здесь, однако, это не перекрывающиеся прямоугольники.Я использую приложение Disk Inventory X, оно использует ту же концепцию для визуализации файловой системы.
Прошу прощения за мое невежество и неспособность правильно построить запрос Google, может кто-нибудь объяснить, как это связано с реальным миром?реализации?
Если предположить, что именно так файлы располагаются на диске, каковы реальные требования к входным данным и потребляемому времени / памяти?
Большое спасибо!