Устройство для решения задачи о рюкзаке

Устройство для решения задачи о рюкзаке

Реферат

Изобретение относится к вычислительной технике и предназначено для моделирования процесса заполнения рюкзака (контейнера, баржи, транспортного самолета и т.п.) различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака.

Известно устройство для выбора варианта испытаний технических устройств (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), содержащее регистры сдвига, блок формирования перестановок, блок постоянной памяти, блок запоминания лучшего варианта, коммутатор, арифметико-логическое устройство, электронную модель графа, группу элементов ИЛИ, дешифратор выбора дуги, реверсивный счетчик ячеек, блок оперативной памяти, счетчик топологии, счетчики расстояний, умножитель, сумматор, регистр минимальной длины связей, элементы сравнения, вычитатель, триггер начала счета, триггер режима, триггер задания топологии, регистр длины связей, счетчик дуг, дешифратор блокировки дуги, регистр номера дуги, регистр минимального веса, группы элементов И, одновибраторы, элементы задержки. Устройство предназначено для моделирования комбинаторных задач при проектировании радиоэлектронной аппаратуры за счет введения средств для формирования размещения взвешенных графов в линейной и кольцевой топологической модели, а также средств для оценки степени близости сформированного размещения к оптимальному.

Недостатком данного устройства является невозможность моделирования процесса заполнения рюкзака различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака.

Наиболее близким устройством того же назначения к заявленному изобретению по совокупности признаков является, принятое за прототип, устройство для решения задачи о рюкзаке (RU №2413287 C2, МПК G06F 15/00, G06N 7/00, заявлено 19.01.2009, опубл. 27.02.2011, Бюл. №6), содержащее генератор тактовых импульсов 1, группу из m счетчиков 4₁, 4₂,…,4_m, группы из m первых 5₁, 5₂,…,5_m, вторых 6₁, 6₂,…,6_m, третьих 7₁, 7₂,…,7_m регистров, четвертый 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, группу из m счетчиков 4₁, 4₂, …, 4_m, группы из m первых 5₁, 5₂, …, 5_m, вторых 6₁, 6₂, …, 6_m, третьих 7₁, 7₂, …, 7_m регистров, четвертый 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_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, девятый регистр 13, группы из m третьих 16₁, 16₂, …, 16_m и четвертых 17₁, 17₂, …, 17_m сумматоров, группа из m третьих схем сравнения 20₁, 20₂, …, 20_m, вход сброса устройства 23, группа из m вторых выходов устройства 25₁, 25₂, …, 25_m, третьи выходы устройства 26, четвертые выходы устройства 27, причем вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 4₁, 4₂, …, 4_m, третьими входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, третьими входами пятого 9 и девятого 13 регистров, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4₁, 4₂, …, 4_m, первыми входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, первыми входами пятого 9 и девятого 13 регистров, вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 4₁, третьим входом первой схемы сравнения 20₁ из третьей группы схем сравнения, вторыми входами первых регистров 11₁ и 12₁ из седьмой и восьмой групп регистров, выход каждого счетчика 4_i (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5_i и второму входу группы третьих схем сравнения 20_i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10_i, выход группы третьих схем сравнения 20_i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4_i, четвертыми входами групп седьмых 11_i и восьмых 12_i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20_i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20_i+1, вторыми входами разрешения записи группы счетчиков 4_i+1 и вторыми входами разрешения записи групп седьмых 11_i+1 и восьмых 12_i+1 регистров, выход группы вторых регистров 6_i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16_i, выход которого соединен с пятым информационным входом группы седьмых регистров 11_i, выход которого соединен со вторым входом группы третьих сумматоров 16_i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7_i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17_i, выход которого соединен с пятым информационным входом группы восьмых регистров 12_i, выход которого соединен со вторым входом группы четвертых сумматоров 17_i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5_i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20_m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3, выход которого является первым выходом устройства 24, выходы группы из m первых 5₁, 5₂, …, 5_m регистров являются группой из m вторых выходов 25₁, 25₂, …, 25_m устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.

На фиг.1 представлена схема предлагаемого устройства для решения задачи о рюкзаке.

На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из m счетчиков 4₁, 4₂, …, 4_m, группы из m первых 5₁, 5₂, …, 5_m, вторых 6₁, 6₂, …, 6_m, третьих 7₁, 7₂, …, 7_m регистров, четвертый 8 и пятый 9 регистры, группы из m шестых 10₁, 10₂, …, 10_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, девятый регистр 13, первый 14 и второй 15 сумматоры, группы из m третьих 16₁, 16₂, …, 16_m и четвертых 17₁, 17₂, …, 17_m сумматоров, первая 18 и вторая 19 схемы сравнения, группа из m третьих схем сравнения 20₁, 20₂, …, 20_m, элемент И 21, вход пуска устройства 22, вход сброса устройства 23, первый выход устройства 24, группа из m вторых выходов устройства 25₁, 25₂, …, 25_m, третьи выходы устройства 26, четвертые выходы устройства 27. Выход ГТИ 1 соединен с входами синхронизации группы счетчиков и соответствующих групп регистров. Внешний вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние группы счетчиков и соответствующих групп регистров.

Выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21.

Вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 4₁, 4₂, …, 4_m, третьими входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, третьими входами пятого 9 и девятого 13 регистров. Выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4₁, 4₂, …, 4_m, первыми входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, первыми входами пятого 9 и девятого 13 регистров.

Вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 4₁, третьим входом первой схемы сравнения 20₁ из третьей группы схем сравнения, вторыми входами первых регистров 11₁ и 12₁ из седьмой и восьмой групп регистров.

Выход каждого счетчика 4_i (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5_i и второму входу группы третьих схем сравнения 20_i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10_i, выход группы третьих схем сравнения 20_i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4_i, четвертыми входами групп седьмых 11_i и восьмых 12_i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20_i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20_i+1, вторыми входами разрешения записи группы счетчиков 4_i+1 и вторыми входами разрешения записи групп седьмых 11_i+1 и восьмых 12_i+1 регистров, выход группы вторых регистров 6_i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16_i, выход которого соединен с пятым информационным входом группы седьмых регистров 11_i, выход которого соединен со вторым входом группы третьих сумматоров 16_i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7_i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17_i, выход которого соединен с пятым информационным входом группы восьмых регистров 12_i, выход которого соединен со вторым входом группы четвертых сумматоров 17_i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5_i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20_m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3.

Выход триггера готовности результата 3 является первым выходом устройства 24, выходы группы из m первых 5₁, 5₂, …, 5_m регистров являются группой из m вторых выходов 25₁, 25₂, …, 25_m устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.

Предлагаемое устройство для решения задачи о рюкзаке работает следующим образом.

В устройстве моделируется заполнение рюкзака из m групп различных предметов, для каждой из которых задается вес единицы v_i, цена единицы s_i, допустимое количество предметов n_i (i=1, 2, …, m, где m - число групп предметов). Результатом работы устройства является определение максимальной суммарной стоимости S_max заполненного рюкзака количеством k_i предметов i-го типа, помещенных в рюкзак, при ограничении на суммарный вес рюкзака V_max.

В исходном состоянии на каждом регистре в группах из m вторых регистров 6₁, 6₂, …, 6_m устанавливается код цены единицы s_i соответствующего предмета, третьих регистров 7₁, 7₂, …, 7_m устанавливается код веса единицы v_i, шестых регистров 10₁, 10₂, …, 10_m устанавливается код допустимого количества предметов n_i соответствующей i-й группы. На четвертом регистре 8 устанавливается код максимального допустимого веса рюкзака V_max. Группы вторых регистров 6₁, 6₂, …, 6_m, третьих регистров 7₁, 7₂, …, 7_m, шестых регистров 10₁, 10₂, …, 10_m и четвертый регистр 8 могут быть выполнены на клавишных регистрах.

Группа счетчиков 4₁, 4₂, …, 4_m предназначена для задания текущих значений количества предметов из возможных n_i соответствующей i-й группы. В процессе моделирования в группах седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров накапливаются текущие стоимость S_{i гр} и вес V_{i гр} для набора предметов i-й группы. В группе первых регистров 5₁, 5₂, …, 5_m фиксируется код количества предметов k_i, в пятом регистре 9 фиксируется значение максимальной стоимости S_max, а в девятом регистре 13 фиксируется значение общего веса V набора предметов для заполненного рюкзака.

В m группах, состоящих из элементов счетчика 4_i, шестых регистров 10_i и третьих схем сравнения 20_i и соответствующих связях, реализуется счетчик с заданным модулем, равным допустимому количеству предметов n_i в i-й группе. При достижении счетчиком 4_i значения допустимого кода n_i на выходе схемы сравнения 20_i формируется единичный сигнал CE_i=1, по которому проводится синхронная установка в нулевое состояние одноименного счетчика 4_i (i=1, 2, …, m), разрешается увеличение счетчика 4_i+1, разрешается работа третьей схемы сравнения 20_i+1, проводится запись текущего веса V_{i+1 гр} в восьмой регистр 12_i+1 и текущей стоимости S_{i+1 гр} в седьмой регистр 11_i+1 в (i+1)-й группе (i=1, 2, …, m-1).

В m группах, состоящих из элементов вторых регистров 6_i, седьмых регистров 11_i, третьих сумматоров 16_i и соответствующих связях, реализуется вычисление текущей стоимости i-й группы (i=1, 2, …, m), которая вычисляется увеличением предыдущей стоимости группы S_{i гр} на цену единицы группы s_i, и фиксация значения текущей стоимости i-й группы на седьмом регистре 11_i. Аналогично в m группах, состоящих из элементов третьих регистров 7_i, восьмых регистров 12_i, четвертых сумматоров 17_i и соответствующих связях, реализуется вычисление текущего веса V_{i гр} i-й группы и фиксация этого значения веса группы на регистре 12_i.

Импульсы с ГТИ 1 постоянно поступают на входы синхронизации счетчиков и регистров, режимы работы которых задаются сигналами на соответствующих входах управления.

При подаче сигнала на вход сброса устройства 23 по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 4₁, 4₂, …, 4_m, группы первых регистров 5₁, 5₂, …, 5_m, пятый регистр 9, группы седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, девятый регистр 13.

Работа устройства начинается после подачи сигнала ПУСК на вход устройства 22, по которому синхронно с импульсом от ГТИ 1 устанавливается в единичное состояние выход триггера разрешения 2, который соединен с входом разрешения счета первого счетчика 4₁, входом разрешения схемы сравнения 20₁ и входами разрешения записи в седьмой 11₁ и восьмой 12₁ регистры.

На следующих тактах ГТИ 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_max=11.

При достижении первым счетчиком 4₁ значения модуля n₁, записанного в регистре 10₁, на выходе схемы сравнения 20₁ формируется сигнал СЕ1=1 (в таблице 1 такты 3, 7, 11, …), по которому на следующем такте счетчик 4₁ устанавливается в нулевое состояние, разрешается увеличение счетчика 4₂ и сравнение на схеме 20₂, а также проводится запись текущих значений стоимости S_{2-й гр} и веса V_{2-й гр} для 2-й группы в регистры 11₂ и 12₂.

Аналогично при достижении вторым счетчиком 4₂ значения модуля n₂, записанного в регистре 10₂, на выходе схемы сравнения 20₂ формируется сигнал СЕ2=1 (в таблице 1 такты 7, 15, 23), по которому на следующем такте счетчик 4₂ устанавливается в нулевое состояние, разрешается увеличение счетчика 4₃ и сравнение на схеме 20₃, а также проводится запись текущих значений стоимости S_{3-й гр} и веса V_{3-й гр} для 3-й группы в регистры 11₃ и 12₃, и т.д. моделируется для последующих групп.

Одновременно коды стоимости групп с седьмых регистров 11₁, 11₂, …, 11_m и весов групп с восьмых регистров 12₁, 12₂, …, 12_m поступают соответственно на одноименные входы второго 15 и первого 14 сумматоров, на выходах которых формируется значение общей текущей стоимости S_тек и общего текущего веса V_тек всех групп набора предметов в рюкзаке.

Код значения общего текущего веса V_тек всех групп с выхода первого сумматора 14 поступает на первый вход первой схемы сравнения 18, на второй вход которой поступает код с выхода регистра 8 со значением допустимого веса рюкзака. Единичный сигнал СС1=1 на выходе первой схемы сравнения 18 формируется только в том случае, если код текущего веса рюкзака V_тек на выходе первого сумматора 14 меньше или равен коду допустимого веса рюкзака V_max на выходе регистра 8. В таблице 1 общий вес рюкзака V_тек превышает допустимый вес рюкзака V_max=11 только на тактах 15 и 23, поэтому на остальных тактах на выходе первой схемы сравнения 18 формируется сигнал СС1=1.

Код значения общей стоимости S_тек всех групп с выхода второго сумматора 15 поступает на первый вход второй схемы сравнения 19, на второй вход которой поступает код с выхода регистра 9 со значением стоимости S_max рюкзака, зафиксированной на предыдущих тактах как максимальная стоимость. Единичный сигнал СС2=1 на выходе второй схемы сравнения 19 формируется только в том случае, если код общей текущей стоимости S_тек на выходе второго сумматора 15 больше или равен коду стоимости рюкзака S_max на выходе регистра 9. В таблице 1 общая текущая стоимость S_тек рюкзака равна или превышает стоимость S_max, зафиксированную в регистре 9 на тактах 1-7, 13-15, 19-23, поэтому на данных тактах на выходе второй схемы сравнения 19 формируется сигнал СС2=1.

Сигналы с выходов первой 18 и второй 19 схем сравнения поступают на входы элемента И 21, на выходе которого единичный сигнал EN=1 формируется в случае единичных входных сигналов. В этом случае общий текущий вес V_тек всех групп не превышает допустимый вес рюкзака V_max. И общая стоимость S_тек всех групп равна или превышает стоимость предыдущего набора предметов, зафиксированную в регистре 9.

Единичный сигнал EN=1 на выходе элемента 21 разрешает запись в группу первых регистров 5₁, 5₂, …, 5_m с выходов счетчиков 4₁, 4₂, …, 4_m текущих значений k_i количества предметов i-го типа в рюкзаке, запись общего текущего веса V_тек всех групп в регистр 13, запись кода максимальной текущей стоимости S_max набора предметов в рюкзаке в регистр 9. При равенстве текущей и максимальной стоимости наборов и допустимом весе рюкзака в регистры 5_i, 9, 13 будут записаны данные по последнему (текущему) набору предметов (в таблице 1 это такты 14, 20, 21).

При достижении счетчиком 4_m максимального значения на выходе схемы сравнения 20_m формируется сигнал CE_m=1, который поступает на синхронные вход установки в нулевое состояние триггера разрешения 2 и вход установки в единичное состояние триггера готовности результата 3, в результате чего на выходе устройства 24 формируется сигнал ГОТОВ об окончании работы устройства. Нулевое значение сигнала на выходе триггера 2 останавливает счетный режим счетчика 4₁, а следовательно, и других счетчиков 4₂, …, 4_m, которые последовательно соединены сигналами СЕ1, CE2, …, CE_m-1.

В таблице 1 итоговая запись набора предметов в выходные регистры была получена на такте 23, при этом получено: максимальная стоимость S_max=9, вес набора предметов V=10, количество предметов по группам - k₁=2, k₂=1, k₃=2.

В результате работы устройства будут установлены:

сигнал ГОТОВ окончания работы устройства 24;

коды количества k_i предметов набора i-го типа (i=1, …, m) заполненного рюкзака на выходах 25₁, 25₂, …, 25_m;

значение максимальной стоимости S_max набора предметов в рюкзаке на выходах 26;

значение общего веса V набора предметов в рюкзаке на выходах 27.

В предлагаемом устройстве вычисление текущих значений веса V_тек и стоимости групп S_тек проводится на сумматоре сложением стоимости S_{i-й гр} и веса V_{i-й гр} 1-й группы, полученных на предыдущем такте, и соответственно цены s_i и веса v_i единицы i-й группы, так как на каждом такте моделирования количество предметов в наборе может увеличиваться только на одну единицу в каждой группе. В прототипе текущие значения стоимости S_{i-й гр} и веса V_{i-й гр} i-й группы вычисляются в блоках умножения на каждом шаге, как произведение цены s_i и веса v_i единицы на текущее количество предметов k_i в i-й группе. При реализации блоков умножения необходимо значительно больше аппаратных и временных затрат на вычисление, в сравнении с сумматором в заявляемом устройстве. Кроме того, в предлагаемом устройстве, в отличие от прототипа, на девятом регистре 13 после завершения моделирования будет зафиксирован итоговый вес V набора предметов заполненного рюкзака, а также имеется возможность задания допустимого количества предметов n_i в каждой группе предметов на регистрах 10₁, 10₂, …, 10_m шестой группы.

Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для решения задачи о рюкзаке обладает регулярностью узлов и связей и соответствует заявляемому техническому результату - сокращение аппаратных затрат, увеличение быстродействия и расширение функциональных возможностей.

Таблица 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 группа (41)	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 группа (42)	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 группа (43)	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 (201)	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 (202)	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 (203)	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 группа (111)	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 группа (112)	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 группа (113)	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 группа (121)	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 группа (122)	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 группа (123)	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 группа (51)	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 группа (52)	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 группа (53)	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

Устройство для решения задачи о рюкзаке, содержащее генератор тактовых импульсов (ГТИ) 1, группу из m счетчиков 4₁, 4₂, …, 4_m, группы из m первых 5₁, 5₂, …, 5_m, вторых 6₁, 6₂, …, 6_m, третьих 7₁, 7₂, …, 7_m регистров, четвертый 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_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, девятый регистр 13, группы из m третьих 16₁, 16₂, …, 16_m и четвертых 17₁, 17₂, …, 17_m сумматоров, группа из m третьих схем сравнения 20₁, 20₂, …, 20_m, вход сброса устройства 23, группа из m вторых выходов устройства 25₁, 25₂, …, 25_m, третьи выходы устройства 26, четвертые выходы устройства 27, причем вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 4₁, 4₂, …, 4_m, третьими входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, третьими входами пятого 9 и девятого 13 регистров, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 4₁, 4₂, …, 4_m, первыми входами групп из m первых 5₁, 5₂, …, 5_m, седьмых 11₁, 11₂, …, 11_m и восьмых 12₁, 12₂, …, 12_m регистров, первыми входами пятого 9 и девятого 13 регистров, вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 4₁, третьим входом первой схемы сравнения 20₁ из третьей группы схем сравнения, вторыми входами первых регистров 11₁ и 12₁ из седьмой и восьмой групп регистров, выход каждого счетчика 4₁ (i=1, 2, …, m) подсоединен к информационным входам группы первых регистров 5_i и второму входу группы третьих схем сравнения 20_i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10_i, выход группы третьих схем сравнения 20_i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4_i, четвертыми входами групп седьмых 11_i и восьмых 12_i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20_i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20_i+1, вторыми входами разрешения записи группы счетчиков 4_i+1 и вторыми входами разрешения записи групп седьмых 11_i+1 и восьмых 12_i+1 регистров, выход группы вторых регистров 6_i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16_i, выход которого соединен с пятым информационным входом группы седьмых регистров 11_i, выход которого соединен со вторым входом группы третьих сумматоров 16_i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7_i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17_i, выход которого соединен с пятым информационным входом группы восьмых регистров 12_i, выход которого соединен со вторым входом группы четвертых сумматоров 17_i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5_i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20_m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3, выход которого является первым выходом устройства 24, выходы группы из m первых 5₁, 5₂, …, 5_m регистров являются группой из m вторых выходов 25₁, 25₂, …, 25_m устройства, выходы пятого регистра 9 являются третьими выходам