Вы нашли то, что искали?
Главная Разделы

Добавить страницу в закладки ->
Обязательно посмотрите энциклопедию:

Радиоэлектроника, Схемы радиолюбителям


14.5.4. Задача о рюкзаке. Теоретические основы цифровой связи

Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

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

Классическая задача о рюкзаке изображена на рис. 14.19. Рюкзак наполнен множеством предметов с указанием их веса в граммах. Зная вес наполненного рюкзака (шкала весов градуирована так, что вес пустого рюкзака вычитается), нужно определить содержимое рюкзака. В этом простом примере решение легко найти методом проб и ошибок. Однако если в заданном множестве не 10, а 100 возможных единиц, задача может стать вычислительно неосуществимой.

Рис. 14.19. Задача о рюкзаке

Опишем задачу о рюкзаке через вектор рюкзака и вектор данных. Вектор рюкзака представляет собой n-кортеж разных целых чисел (аналогично множеству разных предметов содержимого рюкзака).

a = a1, a2, …, an

Вектор данных — это n-кортеж двоичных символов.

x = x1, x2, …, xn

Рюкзак S — это сумма подмножества компонентов вектора рюкзака.

ax, где xi = 0,1 (14.40)

Задачу о рюкзаке можно сформулировать следующим образом: при данном S и известном а определите х.

Пример 14.6. Пример рюкзака

Дано а = 1, 2, 4, 8, 16, 32 и S = ах =26. Найдите х.

Решение

Видно, что в этом примере х — это двоичное представление S. Преобразование из десятичного в двоичное окажется более, знакомым, если представить а как 20, 21, 22, 23, 24, 25, 26. Вектор данных х находится легко, поскольку а в этом примере является быстровозрастающим; это означает, что каждый компонент набора n-кортежа а больше суммы предыдущих компонентов. Другими словами,

i = 2,3, ..., п (14.41)

Если а является быстровозрастающим, то первый элемент х - хn = 1, если Sаn (в противном случае, хn=0); следующий элемент находится согласно соотношению

, (14.42)

где i = п-1, п-2,..., 1. С помощью равенства (14.42) легко вычисляется х = 010110.

Пример 14.7. Пример рюкзака

Дано а = 171, 197, 459, 1191, 2410, 4517 и S = ах = 3798. Найдите х.

Решение

Как и в примере 14.6, а является быстровозрастающим. Поэтому с помощью равенства (14.42) можно вычислить х.

х = 010110







© Банк лекций Siblec.ru
Электронная техника, радиотехника и связь. Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки. Карта сайта

Новосибирск, Екатеринбург, Москва, Санкт-Петербург, Нижний Новгород, Ростов-на-Дону, Чебоксары.

E-mail: formyneeds@yandex.ru