Задача о рюкзаке Динамическое программирование. Задача о ранце Общий вес ранца заранее ограничен. Какие предметы положить в ранец, чтобы общая полезность. - презентация

1 Задача о рюкзаке Динамическое программирование

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

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

4 Решить задачу о рюкзаке. Вместимость 9 i 1234 cici 5763 qiqi 2357

5 Решить задачу о рюкзаке. Вместимость 7 i 1234 cici 3264 qiqi 5353

6 i 1234 cici 5254 qiqi 6353

7 Решить задачу о рюкзаке. Вместимость 8 i 1234 cici 7461 qiqi 5135

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

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

10 Пример шифрования Пусть Алиса хочет зашифровать "a". Сначала она должна перевести "a" в двоичный код Далее она умножает каждый бит на соответствующее число из последовательности β, а сумму значений отправляет получателю. a = * * * * * * * * 236 = 1129

11 Расшифровка Чтобы расшифровать сообщение, Боб умножает полученное им значение на мультипликативное обратное r по модулю q * 442 mod 881 = 372 После этого Боб раскладывает 372 следующим образом. Сначала он выбирает наибольший элемент из w, который меньше, чем 372, и вычисляет их разность. Далее он выбирает следующий наибольший элемент, который меньше, чем полученная разность, и повторяет эти действия, пока разность не станет равной нулю = = = 0 Элементы, которые были выбраны из w, будут соответствовать 1 в двоичной записи исходного текста Переводя обратно из двоичной записи, Боб получает, наконец, искомое "a".