Пусть R* обозначает оптимальное значение R, количество использованных раундов. Легко показать, что если N=K*M и M=K*K, то R* = K+1. Пример: K=7, M=49, N=341: Выполнить K=7 раундов с неперекрывающимися группами. K - это наименьшее количество раундов, которое может касаться каждого предмета, но это количество раундов не может доказать, для любого данного предмета, что оно находится или не находится в верхней части K. Следовательно, R* > K для N=K^3 и M=K^2 чехол. Теперь проведите еще один раунд с 7 лучшими предметами из каждого из предыдущих раундов и выберите 7 лучших из этого раунда.
Мне не известен указанный вопрос как «классическая проблема», и я думаю, что мой пример иллюстрирует, что проблема отличается от проблем сложности сортировки типа O (n ln n) и более соответствует медиана или турнирные алгоритмы или алгоритмы выбора . Конечно, имеется большая литература по объединенным алгоритмам тестирования и взвешивания, и некоторые из рассуждений, использованных при решении этих проблем, применимы здесь, но их конкретные методы не применимы.