УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ
KNAPSACK PROBLEM SOLVING DEVICE

Изобретение относится к вычислительной технике и предназначено для моделирования процесса заполнения рюкзака (контейнера, баржи, транспортного самолета и т.п.) различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака.
Известно устройство для выбора варианта испытаний технических устройств (RU №2380745 С1, МПК G06F 15/00, G06F 17/00, заявлено 04.02.2009, опубл. 27.01.2010, Бюл. №3), содержащее генератор тактовых импульсов, три группы входных регистров, три группы блоков умножения, группу сумматоров, три элемента ИЛИ, блок сравнения, группу коммутаторов, группу элементов задержки, элемент НЕ, распределитель импульсов, две группы выходных регистров, две группы блоков индикации. Устройство обеспечивает выбор оптимального варианта с целью минимизации затрат на проведение испытаний с учетом рисков поставщика и заказчика.
Недостатком данного устройства является то, что выбор варианта проводится только по одному критерию - минимизации затрат, а также то, что результирующий выбор варианта проводится путем визуального просмотра показаний группы блоков индикации.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные и временные затраты, связанные с реализацией блоков умножения и временем на выполнение операции умножения в блоках умножения, а также отсутствие средств, обеспечивающих фиксацию выбранного варианта.
Известно устройство для формирования субоптимального размещения и его оценки (RU №2193796 C2, МПК G06F 17/10, G06F 7/38, заявлено 29.01.2001, опубл. 27.11.2002), содержащее регистры сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, электронную модель графа, группу элементов ИЛИ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, элементы сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группы элементов И, одновибраторы, элементы задержки. Устройство предназначено для моделирования комбинаторных задач при проектировании радиоэлектронной аппаратуры за счет введения средств для формирования размещения взвешенных графов в линейной и кольцевой топологической модели, а также средств для оценки степени близости сформированного размещения к оптимальному.
Недостатком данного устройства является невозможность моделирования процесса заполнения рюкзака различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака.
1
2
m
1
2
m
1
2
m
1
2
m
Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для решения задачи о рюкзаке (RU №2413287 C2, МПК G06F 15/00, G06N 7/00, заявлено 19.01.2009, опубл. 27.02.2011, Бюл. №6), содержащее генератор тактовых импульсов 1, группу из m счетчиков 4, 4,…,4, группы из m первых 5, 5,…,5, вторых 6, 6,…,6, третьих 7, 7,…,7 регистров, четвертый 8 и пятый 9 регистры, первый 14 и второй 15 сумматоры, первую 18 и вторую 19 схемы сравнения, элемент И 21, вход пуска устройства 22, первый 24 выход устройства, причем выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21.
Недостатком данного устройства является невозможность в процессе моделирования заполнения рюкзака задавать возможное количество предметов i-го типа (i=1, 2, …, m), а также отсутствует фиксация значения суммарного веса при рассчитанной максимальной стоимости.
К причинам, препятствующим достижению указанного ниже технического результата, относятся большие аппаратные и временные затраты, связанные с реализацией блоков умножения и временем на выполнение операции умножения в блоках умножения на каждом шаге, а также отсутствие средств, обеспечивающих задание допустимого количества предметов i-го типа и фиксацию значения полученного суммарного веса для заполненного рюкзака.
Техническим результатом изобретения является уменьшение аппаратных затрат, увеличение быстродействия устройства и расширение функциональных возможностей.
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
1
1
1
i
i
i
i
i
i
i
i
i
i+1
i+1
i+1
i+1
i
i
i
i
i
i
i
i
i
m
1
2
m
1
2
m
Указанный технический результат при осуществлении изобретения достигается тем, что в устройство для решения задачи о рюкзаке, содержащее генератор тактовых импульсов (ГТИ) 1, группу из m счетчиков 4, 4, …, 4, группы из m первых 5, 5, …, 5, вторых 6, 6, …, 6, третьих 7, 7, …, 7 регистров, четвертый 8 и пятый 9 регистры, первый 14 и второй 15 сумматоры, первую 18 и вторую 19 схемы сравнения, элемент И 21, вход пуска устройства 22, первый 24 выход устройства, выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21, дополнительно введены триггер разрешения 2, триггер готовности результата 3, группы из m шестых 10, 10, …, 10, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, девятый регистр 13, группы из m третьих 16, 16, …, 16 и четвертых 17, 17, …, 17 сумматоров, группа из m третьих схем сравнения 20, 20, …, 20, вход сброса устройства 23, группа из m вторых выходов устройства 25, 25, …, 25, третьи выходы устройства 26, четвертые выходы устройства 27, причем вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 4, 4, …, 4, третьими входами групп из m первых 5, 5, …, 5, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, третьими входами пятого 9 и девятого 13 регистров, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4, 4, …, 4, первыми входами групп из m первых 5, 5, …, 5, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, первыми входами пятого 9 и девятого 13 регистров, вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 4, третьим входом первой схемы сравнения 20 из третьей группы схем сравнения, вторыми входами первых регистров 11 и 12 из седьмой и восьмой групп регистров, выход каждого счетчика 4 (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5 и второму входу группы третьих схем сравнения 20, первый информационный вход которой подсоединен к выходу группы шестых регистров 10, выход группы третьих схем сравнения 20 соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4, четвертыми входами групп седьмых 11 и восьмых 12 регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20 (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20, вторыми входами разрешения записи группы счетчиков 4 и вторыми входами разрешения записи групп седьмых 11 и восьмых 12 регистров, выход группы вторых регистров 6 (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16, выход которого соединен с пятым информационным входом группы седьмых регистров 11, выход которого соединен со вторым входом группы третьих сумматоров 16 и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7 (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17, выход которого соединен с пятым информационным входом группы восьмых регистров 12, выход которого соединен со вторым входом группы четвертых сумматоров 17 и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5 (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20 также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3, выход которого является первым выходом устройства 24, выходы группы из m первых 5, 5, …, 5 регистров являются группой из m вторых выходов 25, 25, …, 25 устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.
На фиг.1 представлена схема предлагаемого устройства для решения задачи о рюкзаке.
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из m счетчиков 4, 4, …, 4, группы из m первых 5, 5, …, 5, вторых 6, 6, …, 6, третьих 7, 7, …, 7 регистров, четвертый 8 и пятый 9 регистры, группы из m шестых 10, 10, …, 10, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, девятый регистр 13, первый 14 и второй 15 сумматоры, группы из m третьих 16, 16, …, 16 и четвертых 17, 17, …, 17 сумматоров, первая 18 и вторая 19 схемы сравнения, группа из m третьих схем сравнения 20, 20, …, 20, элемент И 21, вход пуска устройства 22, вход сброса устройства 23, первый выход устройства 24, группа из m вторых выходов устройства 25, 25, …, 25, третьи выходы устройства 26, четвертые выходы устройства 27. Выход ГТИ 1 соединен с входами синхронизации группы счетчиков и соответствующих групп регистров. Внешний вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние группы счетчиков и соответствующих групп регистров.
Выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21.
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
1
2
m
Вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 4, 4, …, 4, третьими входами групп из m первых 5, 5, …, 5, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, третьими входами пятого 9 и девятого 13 регистров. Выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4, 4, …, 4, первыми входами групп из m первых 5, 5, …, 5, седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, первыми входами пятого 9 и девятого 13 регистров.
1
1
1
1
Вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 4, третьим входом первой схемы сравнения 20 из третьей группы схем сравнения, вторыми входами первых регистров 11 и 12 из седьмой и восьмой групп регистров.
i
i
i
i
i
i
i
i
i
i+1
i+1
i+1
i+1
i
i
i
i
i
i
i
i
i
m
Выход каждого счетчика 4 (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5 и второму входу группы третьих схем сравнения 20, первый информационный вход которой подсоединен к выходу группы шестых регистров 10, выход группы третьих схем сравнения 20 соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4, четвертыми входами групп седьмых 11 и восьмых 12 регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20 (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20, вторыми входами разрешения записи группы счетчиков 4 и вторыми входами разрешения записи групп седьмых 11 и восьмых 12 регистров, выход группы вторых регистров 6 (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16, выход которого соединен с пятым информационным входом группы седьмых регистров 11, выход которого соединен со вторым входом группы третьих сумматоров 16 и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7 (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17, выход которого соединен с пятым информационным входом группы восьмых регистров 12, выход которого соединен со вторым входом группы четвертых сумматоров 17 и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5 (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20 также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3.
1
2
m
1
2
m
Выход триггера готовности результата 3 является первым выходом устройства 24, выходы группы из m первых 5, 5, …, 5 регистров являются группой из m вторых выходов 25, 25, …, 25 устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.
Предлагаемое устройство для решения задачи о рюкзаке работает следующим образом.
i
i
i
max
i
max
В устройстве моделируется заполнение рюкзака из m групп различных предметов, для каждой из которых задается вес единицы v, цена единицы s, допустимое количество предметов n (i=1, 2, …, m, где m - число групп предметов). Результатом работы устройства является определение максимальной суммарной стоимости S заполненного рюкзака количеством k предметов i-го типа, помещенных в рюкзак, при ограничении на суммарный вес рюкзака V.
1
2
m
i
1
2
m
i
1
2
m
i
max
1
2
m
1
2
m
1
2
m
В исходном состоянии на каждом регистре в группах из m вторых регистров 6, 6, …, 6 устанавливается код цены единицы s соответствующего предмета, третьих регистров 7, 7, …, 7 устанавливается код веса единицы v, шестых регистров 10, 10, …, 10 устанавливается код допустимого количества предметов n соответствующей i-й группы. На четвертом регистре 8 устанавливается код максимального допустимого веса рюкзака V. Группы вторых регистров 6, 6, …, 6, третьих регистров 7, 7, …, 7, шестых регистров 10, 10, …, 10 и четвертый регистр 8 могут быть выполнены на клавишных регистрах.
1
2
m
i
1
2
m
1
2
m
i гр
i гр
1
2
m
i
max
Группа счетчиков 4, 4, …, 4 предназначена для задания текущих значений количества предметов из возможных n соответствующей i-й группы. В процессе моделирования в группах седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров накапливаются текущие стоимость S и вес V для набора предметов i-й группы. В группе первых регистров 5, 5, …, 5 фиксируется код количества предметов k, в пятом регистре 9 фиксируется значение максимальной стоимости S, а в девятом регистре 13 фиксируется значение общего веса V набора предметов для заполненного рюкзака.
i
i
i
i
i
i
i
i
i
i+1
i+1
i+1 гр
i+1
i+1 гр
i+1
В m группах, состоящих из элементов счетчика 4, шестых регистров 10 и третьих схем сравнения 20 и соответствующих связях, реализуется счетчик с заданным модулем, равным допустимому количеству предметов n в i-й группе. При достижении счетчиком 4 значения допустимого кода n на выходе схемы сравнения 20 формируется единичный сигнал CE=1, по которому проводится синхронная установка в нулевое состояние одноименного счетчика 4 (i=1, 2, …, m), разрешается увеличение счетчика 4, разрешается работа третьей схемы сравнения 20, проводится запись текущего веса V в восьмой регистр 12 и текущей стоимости S в седьмой регистр 11 в (i+1)-й группе (i=1, 2, …, m-1).
i
i
i
i гр
i
i
i
i
i
i гр
i
В m группах, состоящих из элементов вторых регистров 6, седьмых регистров 11, третьих сумматоров 16 и соответствующих связях, реализуется вычисление текущей стоимости i-й группы (i=1, 2, …, m), которая вычисляется увеличением предыдущей стоимости группы S на цену единицы группы s, и фиксация значения текущей стоимости i-й группы на седьмом регистре 11. Аналогично в m группах, состоящих из элементов третьих регистров 7, восьмых регистров 12, четвертых сумматоров 17 и соответствующих связях, реализуется вычисление текущего веса V i-й группы и фиксация этого значения веса группы на регистре 12.
Импульсы с ГТИ 1 постоянно поступают на входы синхронизации счетчиков и регистров, режимы работы которых задаются сигналами на соответствующих входах управления.
1
2
m
1
2
m
1
2
m
1
2
m
При подаче сигнала на вход сброса устройства 23 по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 4, 4, …, 4, группы первых регистров 5, 5, …, 5, пятый регистр 9, группы седьмых 11, 11, …, 11 и восьмых 12, 12, …, 12 регистров, девятый регистр 13.
1
1
1
1
Работа устройства начинается после подачи сигнала ПУСК на вход устройства 22, по которому синхронно с импульсом от ГТИ 1 устанавливается в единичное состояние выход триггера разрешения 2, который соединен с входом разрешения счета первого счетчика 4, входом разрешения схемы сравнения 20 и входами разрешения записи в седьмой 11 и восьмой 12 регистры.
1
1
1
1
1
2
3
1
2
3
1
2
3
max
На следующих тактах ГТИ 1 в регистры 11 и 12 записывается текущее значение стоимости и веса первой группы, вычисляемое на сумматорах 16 и 17. В таблице 1 по тактам ГТИ 1 приведены значения кодов на счетчиках и регистрах и сигналы СЕ и СС на выходах схем сравнения для устройства, состоящего из трех групп, в которых заданы следующие значения параметров: вес единицы в группах - v=3, v=2, v=1; цена единицы в группах - s=1, s=3, s=2; допустимое количество единиц в группах (модуль счетчика) - n=3, n=1, n=2; допустимый суммарный вес рюкзака V=11.
1
1
1
1
1
2
2
2-й гр
2-й гр
2
2
При достижении первым счетчиком 4 значения модуля n, записанного в регистре 10, на выходе схемы сравнения 20 формируется сигнал СЕ1=1 (в таблице 1 такты 3, 7, 11, …), по которому на следующем такте счетчик 4 устанавливается в нулевое состояние, разрешается увеличение счетчика 4 и сравнение на схеме 20, а также проводится запись текущих значений стоимости S и веса V для 2-й группы в регистры 11 и 12.
2
2
2
2
2
3
3
3-й гр
3-й гр
3
3
Аналогично при достижении вторым счетчиком 4 значения модуля n, записанного в регистре 10, на выходе схемы сравнения 20 формируется сигнал СЕ2=1 (в таблице 1 такты 7, 15, 23), по которому на следующем такте счетчик 4 устанавливается в нулевое состояние, разрешается увеличение счетчика 4 и сравнение на схеме 20, а также проводится запись текущих значений стоимости S и веса V для 3-й группы в регистры 11 и 12, и т.д. моделируется для последующих групп.
1
2
m
1
2
m
тек
тек
Одновременно коды стоимости групп с седьмых регистров 11, 11, …, 11 и весов групп с восьмых регистров 12, 12, …, 12 поступают соответственно на одноименные входы второго 15 и первого 14 сумматоров, на выходах которых формируется значение общей текущей стоимости S и общего текущего веса V всех групп набора предметов в рюкзаке.
тек
тек
max
тек
max
Код значения общего текущего веса V всех групп с выхода первого сумматора 14 поступает на первый вход первой схемы сравнения 18, на второй вход которой поступает код с выхода регистра 8 со значением допустимого веса рюкзака. Единичный сигнал СС1=1 на выходе первой схемы сравнения 18 формируется только в том случае, если код текущего веса рюкзака V на выходе первого сумматора 14 меньше или равен коду допустимого веса рюкзака V на выходе регистра 8. В таблице 1 общий вес рюкзака V превышает допустимый вес рюкзака V=11 только на тактах 15 и 23, поэтому на остальных тактах на выходе первой схемы сравнения 18 формируется сигнал СС1=1.
тек
max
тек
max
тек
max
Код значения общей стоимости S всех групп с выхода второго сумматора 15 поступает на первый вход второй схемы сравнения 19, на второй вход которой поступает код с выхода регистра 9 со значением стоимости S рюкзака, зафиксированной на предыдущих тактах как максимальная стоимость. Единичный сигнал СС2=1 на выходе второй схемы сравнения 19 формируется только в том случае, если код общей текущей стоимости S на выходе второго сумматора 15 больше или равен коду стоимости рюкзака S на выходе регистра 9. В таблице 1 общая текущая стоимость S рюкзака равна или превышает стоимость S, зафиксированную в регистре 9 на тактах 1-7, 13-15, 19-23, поэтому на данных тактах на выходе второй схемы сравнения 19 формируется сигнал СС2=1.
тек
max
тек
Сигналы с выходов первой 18 и второй 19 схем сравнения поступают на входы элемента И 21, на выходе которого единичный сигнал EN=1 формируется в случае единичных входных сигналов. В этом случае общий текущий вес V всех групп не превышает допустимый вес рюкзака V. И общая стоимость S всех групп равна или превышает стоимость предыдущего набора предметов, зафиксированную в регистре 9.
1
2
m
1
2
m
i
тек
max
i
Единичный сигнал EN=1 на выходе элемента 21 разрешает запись в группу первых регистров 5, 5, …, 5 с выходов счетчиков 4, 4, …, 4 текущих значений k количества предметов i-го типа в рюкзаке, запись общего текущего веса V всех групп в регистр 13, запись кода максимальной текущей стоимости S набора предметов в рюкзаке в регистр 9. При равенстве текущей и максимальной стоимости наборов и допустимом весе рюкзака в регистры 5, 9, 13 будут записаны данные по последнему (текущему) набору предметов (в таблице 1 это такты 14, 20, 21).
m
m
m
1
2
m
m-1
При достижении счетчиком 4 максимального значения на выходе схемы сравнения 20 формируется сигнал CE=1, который поступает на синхронные вход установки в нулевое состояние триггера разрешения 2 и вход установки в единичное состояние триггера готовности результата 3, в результате чего на выходе устройства 24 формируется сигнал ГОТОВ об окончании работы устройства. Нулевое значение сигнала на выходе триггера 2 останавливает счетный режим счетчика 4, а следовательно, и других счетчиков 4, …, 4, которые последовательно соединены сигналами СЕ1, CE2, …, CE.
max
1
2
3
В таблице 1 итоговая запись набора предметов в выходные регистры была получена на такте 23, при этом получено: максимальная стоимость S=9, вес набора предметов V=10, количество предметов по группам - k=2, k=1, k=2.
В результате работы устройства будут установлены:
сигнал ГОТОВ окончания работы устройства 24;
i
1
2
m
коды количества k предметов набора i-го типа (i=1, …, m) заполненного рюкзака на выходах 25, 25, …, 25;
max
значение максимальной стоимости S набора предметов в рюкзаке на выходах 26;
значение общего веса V набора предметов в рюкзаке на выходах 27.
тек
тек
i-й гр
i-й гр
i
i
i-й гр
i-й гр
i
i
i
i
1
2
m
В предлагаемом устройстве вычисление текущих значений веса V и стоимости групп S проводится на сумматоре сложением стоимости S и веса V 1-й группы, полученных на предыдущем такте, и соответственно цены s и веса v единицы i-й группы, так как на каждом такте моделирования количество предметов в наборе может увеличиваться только на одну единицу в каждой группе. В прототипе текущие значения стоимости S и веса V i-й группы вычисляются в блоках умножения на каждом шаге, как произведение цены s и веса v единицы на текущее количество предметов k в i-й группе. При реализации блоков умножения необходимо значительно больше аппаратных и временных затрат на вычисление, в сравнении с сумматором в заявляемом устройстве. Кроме того, в предлагаемом устройстве, в отличие от прототипа, на девятом регистре 13 после завершения моделирования будет зафиксирован итоговый вес V набора предметов заполненного рюкзака, а также имеется возможность задания допустимого количества предметов n в каждой группе предметов на регистрах 10, 10, …, 10 шестой группы.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для решения задачи о рюкзаке обладает регулярностью узлов и связей и соответствует заявляемому техническому результату - сокращение аппаратных затрат, увеличение быстродействия и расширение функциональных возможностей.
Таблица 1
Такт
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Счетчики
1 группа (4<sub>1</sub>)
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
2 группа (4<sub>2</sub>)
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
3 группа (4<sub>3</sub>)
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
0
Проверка модуля СЧ:
СЕ1 (20<sub>1</sub>)
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
СЕ2 (20<sub>2</sub>)
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
СЕ3 (20<sub>3</sub>)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
Регистры Вес групп:
1 группа (11<sub>1</sub>)
0
3
6
9
0
3
6
9
0
3
6
9
0
3
6
9
0
3
6
9
0
3
6
9
0
2 группа (11<sub>2</sub>)
0
0
0
0
2
2
2
2
0
0
0
0
2
2
2
2
0
0
0
0
2
2
2
2
0
3 группа (11<sub>3</sub>)
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
0
Регистры
Цена групп:
1 группа (12<sub>1</sub>)
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
0
2 группа (12<sub>2</sub>)
0
0
0
0
3
3
3
3
0
0
0
0
3
3
3
3
0
0
0
0
3
3
3
3
0
3 группа (12<sub>3</sub>)
0
0
0
0
0
0
0
0
2
2
2
2
2
2
2
2
4
4
4
4
4
4
4
4
0
Общий вес
0
3
6
9
2
5
8
11
1
4
7
10
3
6
9
12
2
5
8
11
4
7
10
13
0
Общая цена
0
1
2
3
3
4
5
6
2
3
4
5
5
6
7
8
4
5
6
7
7
8
9
10
0
Проверка веса и стоимости:
СС1 (18)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
СС2 (19)
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
0
1
1
1
1
1
0
EN (21)
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
0
0
0
0
1
1
1
1
0
0
Регистры:
1 группа (5<sub>1</sub>)
0
0
1
2
3
0
1
2
3
3
3
3
3
3
1
2
2
2
2
2
3
0
1
2
2
2 группа (5<sub>2</sub>)
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
3 группа (5<sub>3</sub>)
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
2
2
2
2
2
Итоговые:
Вес (13)
0
0
3
6
9
2
5
8
11
11
11
11
11
11
6
9
9
9
9
9
11
4
7
10
10
Стоимость (9)
0
0
1
2
3
3
4
5
6
6
6
6
6
6
6
7
7
7
7
7
7
7
8
9
9