MK
Если m не степень двойки то его легко будет подрезать
Size: a a a
2020 October 25
MK
Просто надо убирать два листа которые дают наименьший выигрыш
MK
И так пока все ненужные не отрежешь
MK
Ну так а строить по уровням?
По уровням
MK
Последний уровень потом подрежешь до нужного размера
ЕВ
ЕВ
Ну можно попробовать, да.
MK
Для каждого промежуточного узла можно хранить выигрыш: разницу между его площадью и суммой площадей разбиений
MK
И потом использовать выигрыш для подрезки
ЕВ
Не уверен, что точное решение не NP задача
А почему такое решение как выше не будет точным?
2020 October 26
MK
А почему такое решение как выше не будет точным?
Ну я не могу доказать, что оно будет точным
MK
Оно локально оптимальное на каждом шаге. Это не значит, что разбиение глобально оптимально
ЕВ
Интересно...🤔🤔🤔
MK
Но на практике думаю будет работать хорошо
ЕВ
Насколько я понял, то нужно будет поддерживать информацию о точках, которые попали в текущий прямоугольник.
А потом через пирамиду проходится волной, чтобы определить оптимальное разбиение этого прямоугольника?
А потом через пирамиду проходится волной, чтобы определить оптимальное разбиение этого прямоугольника?
MK
Да, нужно держать контейнер с точками
MK
Я не знаю сходу как его организовать чтобы быстрее находить разбиение
ЕВ
Ну окей, я понял. Спасибо.
А в теории это решение может быть глобально оптимальным?🤔
А в теории это решение может быть глобально оптимальным?🤔
MK
Ну окей, я понял. Спасибо.
А в теории это решение может быть глобально оптимальным?🤔
А в теории это решение может быть глобально оптимальным?🤔
Теоретически может, пока никто не привел контрпример