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

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

для каждого из них необходимо решить, класть его в ранец или не класть. Для описания решения вводятся булевы переменные Х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

- супервозрастающая последовательность.
Она является основой для генерации закрытого ключа. Посчитаем сумму элементов последовательности. Она равна 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).

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