Достопочтенный SergeyACTIVITI в своём посте поведал нам про такую полезную вещь, как задача о рюкзаке, решение которой с успехом реализовано в решателях COIN-OR или GLPK. А что же внутри?

Итак, пусть у нас есть рюкзак объёма W, и список из n вещей, у каждой из которых есть объём v[i] и стоимость c[i], и каждую из которых можно брать сколько угодно раз. При этом все объёмы и все стоимости будут положительными и целыми. Как же работает алгоритм?

Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.

На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.

Для начала, рассмотрим самый простой, первым приходящий в голову алгоритм. Давайте переберём все степени двойки, и выберем из них максимальную, которая не превосходит числа. Здесь, очевидно, можно воспользоваться монотонностью этого свойства, то есть тем, что если какая-то степень двойки не превосходит числа, то и меньше степени и подавно не превосходят. Поэтому, это метод можно написать очень просто:

int bit1(int x) {
   int t = 1 << 30;
   while (x < t) t >>= 1;
   return t;
}

Тернарный (или троичный) поиск — это алгоритм поиска минимума (или максимума) выпуклой функции на отрезке. Можно искать минимум (максимум) функции от вещественного аргумента, можно минимум (максимум) на массиве. Будем, для определённости, искать минимум функции f(x).

Он многим знаком, а для тех, кто не знает, расскажу вкратце.

Тернарный поиск заключается в следующем. Пусть есть рекурсивная функция search(L, R), которая по двум концам отрезка L, R определяет минимум на орезке [L, R]. Если R — L < eps, то мы уже вычислили точку, где достигается минимум, с точностью eps. Иначе, разделим отрезок [L,R] на три равных по длине отрезка [L, A], [A, B] и [B, R]. Сравним значение в точках А и В. Вспомнив, что функция f выпуклая, можно сделать вывод, что если f(A) > f(B), то минимум лежит на отрезке [A,R]. Иначе — на отрезке [L, B]. В соответсвии с этим, можно рекурсивно запуститься от одного из отрезков [L, B] или [A, R]. Каждый раз длина области поиска уменьшается в полтора раза, значит, минимум на отрезке длины X с точностью eps будет найден за время O(log(X/eps)).

А здесь я хочу рассказать о квадрарном (или четверичном) поиске.