1. Надо ли уведомлять тех, кто загрузил страницу в 19:59? в 20:00:00? 20:00:59? в 20:01?
2. Время/текст уведомления заранее известно или может внезапно появиться новое?
3. по таймзоне сервера или клиента?
Например, уже нашли вариант:
_ 3 3
4 4 3
5 5 5
максимальная высота - 12
Перебираем другие варианты:
5 ? ?
5 ? ?
5 ? ?
максимальная высота - 15
Его не имеет смысла дальше рассматривать. Что бы мы не поставили вместо "?" - лучше не станет.
Vitsliputsli, мой полный перебор - это обычная рекурсивная функция, примерно как factorial() у webymax . Ничего сложного.
В оптимизированном варианте - добавил только один if. Прекращение проверок ветки, если она уже стала хуже ранее найденного. На скриншоте выше видно.
SPL не использовал - расход памяти и так меньше килобайта.
Без рекурсии и другие оптимизации - могу это сделать только если будет какой-то стимул, например, соревнование.
Такой алгоритм оптимизировать сложно, потому что сначала целиком строится вариант, а потом считается его оптимальность. Получается, что строить и считать надо всегда.
Разве что - выход из цикла, когда найдено самое оптимальное разбиение.
Другие виды оптимизации работают, когда построение идет одновременно с подсчетом оптимальности, в этом случае некоторые ветки просто не продолжают вычисления. Подробнее см. в моем ответе
Vitsliputsli,
1. выход из текущей ветки, если ее эффективность хуже ранее найденного варианта. Если сначала ставить большие цилиндры, то мы достигнем этого за меньшее количество операций.
2. сначала рассматривать варианты только из больших цилиндров в одной группе, чтобы как можно быстрее найти более-менее приемлимый вариант, чтобы в последующем быстрее отсекать другие ветки (см. п. 1)
3. если среди оставшихся цилиндров есть с одинаковой высотой, то на этом уровне достаточно проверить только один из них
4. не рассматривать варианты, отличающиеся порядком групп. Эффективнее в 3! (три-факториал), то есть в 6 раз.
5. не рассматривать варианты, отличающиеся порядком цилиндров в группе. Эффективнее в K! * L! * N! (, где K, L, M - количество цилиндров в каждой группе) раз. Для 10 цилиндров это эффективнее в 4!*3!*3! = 864 раз. Для 11 цилиндров - 3456 раз. Для 12 - 13824. Для 13 - 69120. И т.д.
6. оптимизация памяти: SplFixedArray вместо Array
7. оптимизция скорости: использовать foreach и многомерные массивы вместо рекурсивной функции (каждый вызов требует относительно много ресурсов)
Vitsliputsli, "Что тут думать? Прыгать надо!"
Сначала написать полный перебор.
А потом придумывать разные варианты оптимизаций. И сравнивать эффективность с вариантом без этой оптимизации.
Vitsliputsli, я предлагаю для оптимизации поставить 5 в первую группу и проверять все остальные комбинации. Одним из вариантов будет 5+5 в одной группе - дальше в эту группу больше ничего не ставить, потому что она максимально близко к ИМВВ (10 к 10.6). Это позволит значительно уменьшить количество вариантов перебора.
Если же начинать ставить с маленьких (3), то придется проверять ВСЕ варианты.
В иной ситуации при ИМВВ=9 будет выгодно поставить 5 на 5
Заранее мы этого не знаем. Если лучшего варианта пока не найдено - значит пока им будет 5+5 при ИМВВ=9. Возможно, потом найдем вариант лучше
Если интересно проверить теорию на практике, то можем написать свои скрипты для перебора и потом проверить, чей работает быстрее и с меньшим расходом памяти.
webymax, кстати, еще один вариант оптимизации: если среди оставшихся цилиндров есть с одинаковой высотой, то на этом уровне достаточно проверить только один из них.
Vitsliputsli, я не говорил, что самые длинные цилиндры должны быть в разных группах. Я говорил, что надо проверять варианты, начиная с длинных цилиндров.
Например, в вашем варианте поставив в одну группу 3, 3, 3 не имеет смысла пытаться поставить наверх 4 или 5 - это заведомо невыгодно. Лучше сначала поставить в основание 5, а сверху проверять разные комбинации 3, 4 и 5.
Vitsliputsli, нет. Порядок цилиндров никак не влияет на вариант.
Зато "высокие в основании" позволят не проверять множество заведомо невыгодных вариантов.
Для начала написать тупой полный перебор. Функция получает уже расставленные цилиндры и оставшиеся цилиндры. Берет следующий цилиндр и для каждой группы рекурсивно вызывает себя с новой комбинацией. Возвращает полученную расстановку и, возможно, ее эффективность (насколько близко к ИМВВ).
Потом этот алгоритм оптимизировать, чтобы работало быстрее и не проверяло заведомо невыгодные варианты.
Лучше научиться пользоваться xDebug