После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографических методов.
Существует множество разновидностей задачи о ранце, отличия заключаются в условиях, наложенных на рюкзак, предметы или их выбор.
Рюкзак 0-1 (0-1 Knapsack Problem) : не более одного экземпляра каждого предмета
Ограниченный рюкзак (Bounded Knapsack Problem) : не более заданного числа экземпляров каждого предмета
Неограниченный рюкзак (целочисленный рюкзак)(Unbounded Knapsack Problem (integer knapsack)) : произвольное количество экземпляров каждого предмета
Рюкзак с мультивыбором (Multiple-choice Knapsack Problem)
Мультипликативный рюкзак (Multiple Knapsack Problem) : есть несколько рюкзаков, каждый со своим максимальным весом. Каждый предмет можно положить в любой рюкзак или оставить.
Многомерный рюкзак (Multy-dimensional knapsack problem) : вместо веса дано несколько разных ресурсов (например, вес, объём и время укладки). Каждый предмет тратит заданное количество каждого ресурса. Надо выбрать подмножество предметов так, чтобы общие затраты каждого ресурса не превышали максимума по этому ресурсу, и при этом общая ценность предметов была максимальна.
Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны. Криптосистема Lu-Lee была взломана, ее модификация также оказалась небезопасной. Вскрытия. Криптосистема Pieprzyk была взломана аналогичным образом.
Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest, несмотря на "специализированное вскрытие" - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен. Более того, учитывая легкость с которой пали все остальные варианты, доверять устоявшим пока вариантом, по видимому, неосторожно.
