Сверхвозрастающие ранцы

Что такое легкая задача укладки ранца? Если перечень весов предметов представляет собой сверх возрастающую последовательность, то полученную проблему укладки ранца решить очень легко. Сверх возрастающей называется последовательность, в которой каждый член больше суммы всех предыдущих членов. Например, последовательность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9,15,25} -нет.

Решение для сверхвозрастающего ранца найти легко. Возьмем в качестве текущего полный вес, который надо получить, и сравним его с весом самого тяжелого предмета в куче. Если текущий вес меньше веса данного предмета, то не его в рюкзак не кладут. Если текущий вес больше или равен весу этого предмета, то положим его в рюкзак. Уменьшим текущий вес на вес положенного предмета и перейдем к следующему по весу предмету в последовательности. Будем повторять такие шаги, пока процесс не закончится. Если текущий вес уменьшится до нуля, то решение найдено. В противном случае, нет. Например, пусть полный вес рюкзака равен 70, а последовательность весов предметов равна {2,3,6,13,27,52}. Самый большой вес - 52; он меньше 70, поэтому кладем предмет весом 52 в рюкзак. Вычитаем 52 из 70 и получаем 18. Следующий наибольший вес в последовательности равен 27; он больше 18, поэтому предмет весом 27 мы в рюкзак не кладем. Следующий самый тяжелый предмет имеет вес 13; он меньше 18, поэтому предмет весом 13 мы в рюкзак кладем. Вычитаем 13 из 18 и получаем 5. Следующий самый тяжелый предмет имеет вес 6; он больше 5, поэтому предмет весом 6 мы в рюкзак не кладем. Продолжение этого процесса покажет, что предметы весом 2 и 3 кладутся в рюкзак, и полный вес уменьшается до 0, означая, что решение найдено.

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