"Свободный" алгоритм упаковки бина

Question

Не могу придумать, как это назвать, и поэтому мой поиск в Google тоже не выдерживает...

Я делаю что-то вроде основной проблемы с упаковкой мусорного ведра, но с некоторыми изменениями, которые приводят меня в замешательство.

1. Количество ячеек всегда равно 3, и все 3 всегда имеют одинаковые размеры (равные 1/3 суммы всех размеров предметов)
2. Каждый предмет должен быть помещен в корзину
3. Элементы могут быть "фрагментированы" на несколько последовательных корзин, если они не помещаются полностью в корзину. Минимизируйте это.

С этими тремя критериями (особенно с 3), я не уверен, что проблема больше даже NP-сложна, но четвертый критерий делает это, что я называю, "свободной" проблемой.

4. Размеры бинов не должны строго соблюдаться. Если элемент должен быть "переполнен" в корзину, скажем, на 10% от размера корзины, это нормально, но только если он вмещает весь элемент (не переполняйте для фрагментированных элементов).

Это все еще структурированная проблема, или я испортил свои критерии настолько, что это уже вряд ли можно решить?

Если вам интересно, я использую это для визуализации 3 столбцов (корзин) из многих (или нескольких) категорий (элементов), содержащих много (или несколько) ссылок.

Целевым языком является PHP, но пока предпочтительным является псевдокод.

Answer 1

Думаю, я отвечу на свой вопрос ради будущих посетителей...

Loop through items largest to smallest
Does it fit wholly (overstuffing ok) in the first open bin? ...Yes
    Place it
...No
    Does it fit wholly (overstuffing ok) in the next bin? ...Yes
        Place it
    ...No
        Does it fit wholly (overstuffing ok) in the last bin? ...Yes
            Place it
        ...No
            //Place in first open bin, expecting a fragmentation
            Place x "units" of item until bin size reached (no overstuffing)
            Place y "units" of item until bin size reached (no overstuffing), starting at index x into item
            If x+y is still less than item size, place rest in last bin.

Если увеличение бина привело к тому, что индекс вышел за границы, он воспринимается как "нет". Вероятно, не самая лучшая реализация, но до сих пор это хорошо для меня. Очевидно, что этот подход фиксирован для 3 бинов, но я предполагаю, что он может быть разумно расширен до более (конечных) бинов.