Задача о рюкзаке

в ранец, чтобы общая полезность отобранных предметов была максимальна? Вес

каждого предмета известен.
Есть много эквивалентных формулировок. Например, можно вместо ранца рассматривать космический аппарат – спутник Земли, а в качестве предметов - научные приборы. Тогда задача интерпретируется как отбор приборов для запуска на орбиту. Правда, при этом предполагается решенной предварительная задача - оценка сравнительной ценности исследований, для которых нужны те или иные приборы.
С точки зрения экономики предприятия и организации производства более актуальна другая интерпретация задачи о ранце, в которой в качестве «предметов» рассматриваются заказы (или варианты выпуска партий тех или иных товаров), в качестве полезности – прибыль от выполнения того или иного заказа, а в качестве веса – себестоимость заказа.

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

ранец или не класть. Для описания решения вводятся булевы переменные Хk, k = 1,2,…, n (т.е. переменные, принимающие два значения, а именно, 0 и 1). При этом Хk = 1, если предмет размещают в ранце, и Хk = 0, если нет, k = 1,2,…, n. Для каждого предмета известны две константы: Аk - вес k-го предмета, и Сk - полезность k-го предмета, k = 1,2,…, n . Максимально возможную вместимость ранца обозначим В. Оптимизационная задача имеет вид
C1 Х1 + С2 Х2 + С3 Х3 + …. + СnХn → max ,
А1 Х1 + А2 Х2 + А3 Х3 + …. + АnХn ≤ В.
К целочисленному программированию относятся задачи размещения (производственных объектов), теории расписаний, календарного и оперативного планирования, назначения персонала и т.д.

году Ральфом Мерклем и Мартином Хеллманом была разработана Ранцевая криптосистема

Меркля-Хеллмана. Это была одна из первых криптосистем с открытым ключом, но, к сожалению, она оказалась криптографически нестойкой и, как следствие, не приобрела популярности.
«Задача о рюкзаке» заключается в следующем: зная подмножество грузов, уложенных в ранец, легко подсчитать суммарный вес, но, зная вес, непросто определить подмножество грузов.
В алгоритме шифрования не используются типы вещей, и потому результирующий вектор х содержит лишь 0 или 1.
Р.Мерклю удалось получить обратную к числу s функцию, которая давала бы вектор x, зная только некий «секретный» ключ, и он предложил $100 тому, кто сможет раскрыть ранцевую систему Меркля-Хеллмана.
Меркль использовал не произвольную последовательность wi, а супервозрастающую, то есть такую, что wk+1>Σwi, i=1,2,.., k.
Шифрование
– сообщение x = (x1, x2, ..., xn)
- вычисляем y = b1x1 + b2x2 + …+bnxn

354} - супервозрастающая последовательность.
Она является основой для генерации закрытого ключа.

Посчитаем сумму элементов последовательности. Она равна 706.
Далее выберем простое число q, превосходящее полученное нами значение суммы. q = 881
Выберем также число r из интервала [1,q) r = 588.
Построим последовательность β, умножая каждый элемент из последовательности w на r по модулю q.
2 * 588 mod 881 = 235
7 * 588 mod 881 = 592
11 * 588 mod 881 = 301
21 * 588 mod 881 = 14
42 * 588 mod 881 = 28
89 * 588 mod 881 = 353
180 * 588 mod 881 = 120
354 * 588 mod 881 = 236
Получим β = (295, 592, 301, 14, 28, 353, 120, 236).

"a" в двоичный код
01100001
Далее она умножает каждый бит на соответствующее

число из последовательности β, а сумму значений отправляет получателю.
a = 01100001
0 * 235
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
= 1129

обратное r по модулю q.
1129 * 442 mod 881 =

372
После этого Боб раскладывает 372 следующим образом. Сначала он выбирает наибольший элемент из w, который меньше, чем 372, и вычисляет их разность. Далее он выбирает следующий наибольший элемент, который меньше, чем полученная разность, и повторяет эти действия, пока разность не станет равной нулю.
372 - 354 = 18
18 - 11 = 7
7 - 7 = 0
Элементы, которые были выбраны из w , будут соответствовать 1 в двоичной записи исходного текста.
01100001
Переводя обратно из двоичной записи, Боб получает, наконец, искомое "a".