Изобретение относится к вычислительной технике и предназначено для моделирования процесса заполнения рюкзака (контейнера, баржи, транспортного самолета и т.п.) различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака.
Известно устройство для выбора варианта испытаний технических устройств (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 счетчиков 41, 42,…,4m, группы из m первых 51, 52,…,5m, вторых 61, 62,…,6m, третьих 71, 72,…,7m регистров, четвертый 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 счетчиков 41, 42, …, 4m, группы из m первых 51, 52, …, 5m, вторых 61, 62, …, 6m, третьих 71, 72, …, 7m регистров, четвертый 8 и пятый 9 регистры, первый 14 и второй 15 сумматоры, первую 18 и вторую 19 схемы сравнения, элемент И 21, вход пуска устройства 22, первый 24 выход устройства, выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21, дополнительно введены триггер разрешения 2, триггер готовности результата 3, группы из m шестых 101, 102, …, 10m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, девятый регистр 13, группы из m третьих 161, 162, …, 16m и четвертых 171, 172, …, 17m сумматоров, группа из m третьих схем сравнения 201, 202, …, 20m, вход сброса устройства 23, группа из m вторых выходов устройства 251, 252, …, 25m, третьи выходы устройства 26, четвертые выходы устройства 27, причем вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 41, 42, …, 4m, третьими входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, третьими входами пятого 9 и девятого 13 регистров, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 41, 42, …, 4m, первыми входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, первыми входами пятого 9 и девятого 13 регистров, вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 41, третьим входом первой схемы сравнения 201 из третьей группы схем сравнения, вторыми входами первых регистров 111 и 121 из седьмой и восьмой групп регистров, выход каждого счетчика 4i (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5i и второму входу группы третьих схем сравнения 20i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10i, выход группы третьих схем сравнения 20i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4i, четвертыми входами групп седьмых 11i и восьмых 12i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20i+1, вторыми входами разрешения записи группы счетчиков 4i+1 и вторыми входами разрешения записи групп седьмых 11i+1 и восьмых 12i+1 регистров, выход группы вторых регистров 6i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16i, выход которого соединен с пятым информационным входом группы седьмых регистров 11i, выход которого соединен со вторым входом группы третьих сумматоров 16i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17i, выход которого соединен с пятым информационным входом группы восьмых регистров 12i, выход которого соединен со вторым входом группы четвертых сумматоров 17i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3, выход которого является первым выходом устройства 24, выходы группы из m первых 51, 52, …, 5m регистров являются группой из m вторых выходов 251, 252, …, 25m устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.
На фиг.1 представлена схема предлагаемого устройства для решения задачи о рюкзаке.
На фиг.1 приняты следующие обозначения: генератор тактовых импульсов (ГТИ) 1, триггер разрешения 2, триггер готовности результата 3, группа из m счетчиков 41, 42, …, 4m, группы из m первых 51, 52, …, 5m, вторых 61, 62, …, 6m, третьих 71, 72, …, 7m регистров, четвертый 8 и пятый 9 регистры, группы из m шестых 101, 102, …, 10m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, девятый регистр 13, первый 14 и второй 15 сумматоры, группы из m третьих 161, 162, …, 16m и четвертых 171, 172, …, 17m сумматоров, первая 18 и вторая 19 схемы сравнения, группа из m третьих схем сравнения 201, 202, …, 20m, элемент И 21, вход пуска устройства 22, вход сброса устройства 23, первый выход устройства 24, группа из m вторых выходов устройства 251, 252, …, 25m, третьи выходы устройства 26, четвертые выходы устройства 27. Выход ГТИ 1 соединен с входами синхронизации группы счетчиков и соответствующих групп регистров. Внешний вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние группы счетчиков и соответствующих групп регистров.
Выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21.
Вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 41, 42, …, 4m, третьими входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, третьими входами пятого 9 и девятого 13 регистров. Выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 41, 42, …, 4m, первыми входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, первыми входами пятого 9 и девятого 13 регистров.
Вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 41, третьим входом первой схемы сравнения 201 из третьей группы схем сравнения, вторыми входами первых регистров 111 и 121 из седьмой и восьмой групп регистров.
Выход каждого счетчика 4i (i=1, 2, …, m) подсоединен к информационным входам четвертому входу группы первых регистров 5i и второму входу группы третьих схем сравнения 20i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10i, выход группы третьих схем сравнения 20i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4i, четвертыми входами групп седьмых 11i и восьмых 12i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20i+1, вторыми входами разрешения записи группы счетчиков 4i+1 и вторыми входами разрешения записи групп седьмых 11i+1 и восьмых 12i+1 регистров, выход группы вторых регистров 6i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16i, выход которого соединен с пятым информационным входом группы седьмых регистров 11i, выход которого соединен со вторым входом группы третьих сумматоров 16i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17i, выход которого соединен с пятым информационным входом группы восьмых регистров 12i, выход которого соединен со вторым входом группы четвертых сумматоров 17i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3.
Выход триггера готовности результата 3 является первым выходом устройства 24, выходы группы из m первых 51, 52, …, 5m регистров являются группой из m вторых выходов 251, 252, …, 25m устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.
Предлагаемое устройство для решения задачи о рюкзаке работает следующим образом.
В устройстве моделируется заполнение рюкзака из m групп различных предметов, для каждой из которых задается вес единицы vi, цена единицы si, допустимое количество предметов ni (i=1, 2, …, m, где m - число групп предметов). Результатом работы устройства является определение максимальной суммарной стоимости Smax заполненного рюкзака количеством ki предметов i-го типа, помещенных в рюкзак, при ограничении на суммарный вес рюкзака Vmax.
В исходном состоянии на каждом регистре в группах из m вторых регистров 61, 62, …, 6m устанавливается код цены единицы si соответствующего предмета, третьих регистров 71, 72, …, 7m устанавливается код веса единицы vi, шестых регистров 101, 102, …, 10m устанавливается код допустимого количества предметов ni соответствующей i-й группы. На четвертом регистре 8 устанавливается код максимального допустимого веса рюкзака Vmax. Группы вторых регистров 61, 62, …, 6m, третьих регистров 71, 72, …, 7m, шестых регистров 101, 102, …, 10m и четвертый регистр 8 могут быть выполнены на клавишных регистрах.
Группа счетчиков 41, 42, …, 4m предназначена для задания текущих значений количества предметов из возможных ni соответствующей i-й группы. В процессе моделирования в группах седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров накапливаются текущие стоимость Si гр и вес Vi гр для набора предметов i-й группы. В группе первых регистров 51, 52, …, 5m фиксируется код количества предметов ki, в пятом регистре 9 фиксируется значение максимальной стоимости Smax, а в девятом регистре 13 фиксируется значение общего веса V набора предметов для заполненного рюкзака.
В m группах, состоящих из элементов счетчика 4i, шестых регистров 10i и третьих схем сравнения 20i и соответствующих связях, реализуется счетчик с заданным модулем, равным допустимому количеству предметов ni в i-й группе. При достижении счетчиком 4i значения допустимого кода ni на выходе схемы сравнения 20i формируется единичный сигнал CEi=1, по которому проводится синхронная установка в нулевое состояние одноименного счетчика 4i (i=1, 2, …, m), разрешается увеличение счетчика 4i+1, разрешается работа третьей схемы сравнения 20i+1, проводится запись текущего веса Vi+1 гр в восьмой регистр 12i+1 и текущей стоимости Si+1 гр в седьмой регистр 11i+1 в (i+1)-й группе (i=1, 2, …, m-1).
В m группах, состоящих из элементов вторых регистров 6i, седьмых регистров 11i, третьих сумматоров 16i и соответствующих связях, реализуется вычисление текущей стоимости i-й группы (i=1, 2, …, m), которая вычисляется увеличением предыдущей стоимости группы Si гр на цену единицы группы si, и фиксация значения текущей стоимости i-й группы на седьмом регистре 11i. Аналогично в m группах, состоящих из элементов третьих регистров 7i, восьмых регистров 12i, четвертых сумматоров 17i и соответствующих связях, реализуется вычисление текущего веса Vi гр i-й группы и фиксация этого значения веса группы на регистре 12i.
Импульсы с ГТИ 1 постоянно поступают на входы синхронизации счетчиков и регистров, режимы работы которых задаются сигналами на соответствующих входах управления.
При подаче сигнала на вход сброса устройства 23 по фронту импульса с ГТИ 1 в нулевое состояние устанавливаются триггер разрешения 2, триггер готовности результата 3, все счетчики 41, 42, …, 4m, группы первых регистров 51, 52, …, 5m, пятый регистр 9, группы седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, девятый регистр 13.
Работа устройства начинается после подачи сигнала ПУСК на вход устройства 22, по которому синхронно с импульсом от ГТИ 1 устанавливается в единичное состояние выход триггера разрешения 2, который соединен с входом разрешения счета первого счетчика 41, входом разрешения схемы сравнения 201 и входами разрешения записи в седьмой 111 и восьмой 121 регистры.
На следующих тактах ГТИ 1 в регистры 111 и 121 записывается текущее значение стоимости и веса первой группы, вычисляемое на сумматорах 161 и 171. В таблице 1 по тактам ГТИ 1 приведены значения кодов на счетчиках и регистрах и сигналы СЕ и СС на выходах схем сравнения для устройства, состоящего из трех групп, в которых заданы следующие значения параметров: вес единицы в группах - v1=3, v2=2, v3=1; цена единицы в группах - s1=1, s2=3, s3=2; допустимое количество единиц в группах (модуль счетчика) - n1=3, n2=1, n3=2; допустимый суммарный вес рюкзака Vmax=11.
При достижении первым счетчиком 41 значения модуля n1, записанного в регистре 101, на выходе схемы сравнения 201 формируется сигнал СЕ1=1 (в таблице 1 такты 3, 7, 11, …), по которому на следующем такте счетчик 41 устанавливается в нулевое состояние, разрешается увеличение счетчика 42 и сравнение на схеме 202, а также проводится запись текущих значений стоимости S2-й гр и веса V2-й гр для 2-й группы в регистры 112 и 122.
Аналогично при достижении вторым счетчиком 42 значения модуля n2, записанного в регистре 102, на выходе схемы сравнения 202 формируется сигнал СЕ2=1 (в таблице 1 такты 7, 15, 23), по которому на следующем такте счетчик 42 устанавливается в нулевое состояние, разрешается увеличение счетчика 43 и сравнение на схеме 203, а также проводится запись текущих значений стоимости S3-й гр и веса V3-й гр для 3-й группы в регистры 113 и 123, и т.д. моделируется для последующих групп.
Одновременно коды стоимости групп с седьмых регистров 111, 112, …, 11m и весов групп с восьмых регистров 121, 122, …, 12m поступают соответственно на одноименные входы второго 15 и первого 14 сумматоров, на выходах которых формируется значение общей текущей стоимости Sтек и общего текущего веса Vтек всех групп набора предметов в рюкзаке.
Код значения общего текущего веса Vтек всех групп с выхода первого сумматора 14 поступает на первый вход первой схемы сравнения 18, на второй вход которой поступает код с выхода регистра 8 со значением допустимого веса рюкзака. Единичный сигнал СС1=1 на выходе первой схемы сравнения 18 формируется только в том случае, если код текущего веса рюкзака Vтек на выходе первого сумматора 14 меньше или равен коду допустимого веса рюкзака Vmax на выходе регистра 8. В таблице 1 общий вес рюкзака Vтек превышает допустимый вес рюкзака Vmax=11 только на тактах 15 и 23, поэтому на остальных тактах на выходе первой схемы сравнения 18 формируется сигнал СС1=1.
Код значения общей стоимости Sтек всех групп с выхода второго сумматора 15 поступает на первый вход второй схемы сравнения 19, на второй вход которой поступает код с выхода регистра 9 со значением стоимости Smax рюкзака, зафиксированной на предыдущих тактах как максимальная стоимость. Единичный сигнал СС2=1 на выходе второй схемы сравнения 19 формируется только в том случае, если код общей текущей стоимости Sтек на выходе второго сумматора 15 больше или равен коду стоимости рюкзака Smax на выходе регистра 9. В таблице 1 общая текущая стоимость Sтек рюкзака равна или превышает стоимость Smax, зафиксированную в регистре 9 на тактах 1-7, 13-15, 19-23, поэтому на данных тактах на выходе второй схемы сравнения 19 формируется сигнал СС2=1.
Сигналы с выходов первой 18 и второй 19 схем сравнения поступают на входы элемента И 21, на выходе которого единичный сигнал EN=1 формируется в случае единичных входных сигналов. В этом случае общий текущий вес Vтек всех групп не превышает допустимый вес рюкзака Vmax. И общая стоимость Sтек всех групп равна или превышает стоимость предыдущего набора предметов, зафиксированную в регистре 9.
Единичный сигнал EN=1 на выходе элемента 21 разрешает запись в группу первых регистров 51, 52, …, 5m с выходов счетчиков 41, 42, …, 4m текущих значений ki количества предметов i-го типа в рюкзаке, запись общего текущего веса Vтек всех групп в регистр 13, запись кода максимальной текущей стоимости Smax набора предметов в рюкзаке в регистр 9. При равенстве текущей и максимальной стоимости наборов и допустимом весе рюкзака в регистры 5i, 9, 13 будут записаны данные по последнему (текущему) набору предметов (в таблице 1 это такты 14, 20, 21).
При достижении счетчиком 4m максимального значения на выходе схемы сравнения 20m формируется сигнал CEm=1, который поступает на синхронные вход установки в нулевое состояние триггера разрешения 2 и вход установки в единичное состояние триггера готовности результата 3, в результате чего на выходе устройства 24 формируется сигнал ГОТОВ об окончании работы устройства. Нулевое значение сигнала на выходе триггера 2 останавливает счетный режим счетчика 41, а следовательно, и других счетчиков 42, …, 4m, которые последовательно соединены сигналами СЕ1, CE2, …, CEm-1.
В таблице 1 итоговая запись набора предметов в выходные регистры была получена на такте 23, при этом получено: максимальная стоимость Smax=9, вес набора предметов V=10, количество предметов по группам - k1=2, k2=1, k3=2.
В результате работы устройства будут установлены:
сигнал ГОТОВ окончания работы устройства 24;
коды количества ki предметов набора i-го типа (i=1, …, m) заполненного рюкзака на выходах 251, 252, …, 25m;
значение максимальной стоимости Smax набора предметов в рюкзаке на выходах 26;
значение общего веса V набора предметов в рюкзаке на выходах 27.
В предлагаемом устройстве вычисление текущих значений веса Vтек и стоимости групп Sтек проводится на сумматоре сложением стоимости Si-й гр и веса Vi-й гр 1-й группы, полученных на предыдущем такте, и соответственно цены si и веса vi единицы i-й группы, так как на каждом такте моделирования количество предметов в наборе может увеличиваться только на одну единицу в каждой группе. В прототипе текущие значения стоимости Si-й гр и веса Vi-й гр i-й группы вычисляются в блоках умножения на каждом шаге, как произведение цены si и веса vi единицы на текущее количество предметов ki в i-й группе. При реализации блоков умножения необходимо значительно больше аппаратных и временных затрат на вычисление, в сравнении с сумматором в заявляемом устройстве. Кроме того, в предлагаемом устройстве, в отличие от прототипа, на девятом регистре 13 после завершения моделирования будет зафиксирован итоговый вес V набора предметов заполненного рюкзака, а также имеется возможность задания допустимого количества предметов ni в каждой группе предметов на регистрах 101, 102, …, 10m шестой группы.
Вышеизложенные сведения позволяют сделать вывод, что предлагаемое устройство для решения задачи о рюкзаке обладает регулярностью узлов и связей и соответствует заявляемому техническому результату - сокращение аппаратных затрат, увеличение быстродействия и расширение функциональных возможностей.
| название | год | авторы | номер документа |
|---|---|---|---|
| УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ | 2013 |
|
RU2518998C1 |
| УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФИКА РАБОТЫ СОТРУДНИКОВ УЧРЕЖДЕНИЯ | 2013 |
|
RU2526005C1 |
| Устройство для решения задачи о рюкзаке | 2015 |
|
RU2613854C1 |
| УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О НАЗНАЧЕНИЯХ | 2012 |
|
RU2511412C1 |
| УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ | 2014 |
|
RU2542661C1 |
| УСТРОЙСТВО ДЛЯ ДЕТЕКТИРОВАНИЯ ГРУПП БИТ В БИНАРНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ | 2020 |
|
RU2728957C1 |
| УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ | 2010 |
|
RU2443013C1 |
| УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧИ О РЮКЗАКЕ | 2009 |
|
RU2413287C2 |
| УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФИКА РАБОТЫ СОТРУДНИКОВ УЧРЕЖДЕНИЯ | 2010 |
|
RU2434273C1 |
| УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФИКА РАБОТЫ СОТРУДНИКОВ УЧРЕЖДЕНИЯ | 2011 |
|
RU2480827C1 |
Изобретение относится к вычислительной технике и предназначено для моделирования процесса заполнения рюкзака (контейнера, баржи, транспортного самолета и т.п.) различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака. Техническим результатом изобретения является уменьшение аппаратных затрат, увеличение быстродействия устройства, расширение функциональных возможностей в части возможности вычисления итогового веса набора предметов, а также в части возможности задания допустимого количества предметов в каждой группе предметов. Устройство для решения задачи о рюкзаке содержит генератор тактовых импульсов, триггер разрешения, триггер готовности результата, группу из m счетчиков, группы из m первых, вторых и третьих регистров, четвертый и пятый регистры, группы из m шестых, седьмых и восьмых регистров, девятый регистр, первый и второй сумматоры, группы из m третьих и четвертых сумматоров, первую и вторую схемы сравнения, группу из m третьих схем сравнения, элемент И, вход пуска устройства, вход сброса устройства, первый выход устройства, группа из m вторых выходов устройства, третьи выходы устройства, четвертые выходы устройства. 1 ил., 1 табл.
Устройство для решения задачи о рюкзаке, содержащее генератор тактовых импульсов (ГТИ) 1, группу из m счетчиков 41, 42, …, 4m, группы из m первых 51, 52, …, 5m, вторых 61, 62, …, 6m, третьих 71, 72, …, 7m регистров, четвертый 8 и пятый 9 регистры, первый 14 и второй 15 сумматоры, первую 18 и вторую 19 схемы сравнения, элемент И 21, вход пуска устройства 22, первый 24 выход устройства, выходы первого сумматора 14 соединены с первыми входами первой схемы сравнения 18, вторые входы которой соединены с выходами четвертого регистра 8, а выход первой схемы сравнения 18 соединен с первым входом элемента И 21, выходы второго сумматора 15 соединены с первыми входами второй схемы сравнения 19, вторые входы которой соединены с выходами пятого регистра 9, а выход второй схемы сравнения 19 соединен со вторым входом элемента И 21, отличающееся тем, что в него дополнительно введены триггер разрешения 2, триггер готовности результата 3, группы из m шестых 101, 102, …, 10m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, девятый регистр 13, группы из m третьих 161, 162, …, 16m и четвертых 171, 172, …, 17m сумматоров, группа из m третьих схем сравнения 201, 202, …, 20m, вход сброса устройства 23, группа из m вторых выходов устройства 251, 252, …, 25m, третьи выходы устройства 26, четвертые выходы устройства 27, причем вход сброса устройства 23 соединен с входами синхронной установки в нулевое состояние третьим входом триггера разрешения 2, третьим входом триггера готовности результата 3, третьими входами группы счетчиков 41, 42, …, 4m, третьими входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, третьими входами пятого 9 и девятого 13 регистров, выход ГТИ 1 соединен с входами синхронизации первым входом триггера разрешения 2, первым входом триггера готовности результата 3, первыми входами группы счетчиков 41, 42, …, 4m, первыми входами групп из m первых 51, 52, …, 5m, седьмых 111, 112, …, 11m и восьмых 121, 122, …, 12m регистров, первыми входами пятого 9 и девятого 13 регистров, вход пуска устройства 22 соединен со вторым входом разрешения работы триггера разрешения 2, выход которого соединен с входами разрешения работы вторым входом первого счетчика 41, третьим входом первой схемы сравнения 201 из третьей группы схем сравнения, вторыми входами первых регистров 111 и 121 из седьмой и восьмой групп регистров, выход каждого счетчика 41 (i=1, 2, …, m) подсоединен к информационным входам группы первых регистров 5i и второму входу группы третьих схем сравнения 20i, первый информационный вход которой подсоединен к выходу группы шестых регистров 10i, выход группы третьих схем сравнения 20i соединен с входами синхронной установки в нулевое состояние четвертым входом группы счетчика 4i, четвертыми входами групп седьмых 11i и восьмых 12i регистров (i=1, 2, …, m), а также выход группы третьих схем сравнения 20i (i=1, 2, …, m-1) соединен с третьим входом разрешения группы третьих схем сравнения 20i+1, вторыми входами разрешения записи группы счетчиков 4i+1 и вторыми входами разрешения записи групп седьмых 11i+1 и восьмых 12i+1 регистров, выход группы вторых регистров 6i (i=1, 2, …, m) подсоединен к первому входу группы третьих сумматоров 16i, выход которого соединен с пятым информационным входом группы седьмых регистров 11i, выход которого соединен со вторым входом группы третьих сумматоров 16i и одноименным входом второго сумматора 15, выход которого подсоединен к четвертому информационному входу пятого регистра 9, выход группы третьих регистров 7i (i=1, 2, …, m) подсоединен к первому входу группы четвертых сумматоров 17i, выход которого соединен с пятым информационным входом группы восьмых регистров 12i, выход которого соединен со вторым входом группы четвертых сумматоров 17i и одноименным входом первого сумматора 14, выход которого подсоединен к четвертому информационному входу девятого регистра 13, выход элемента И 21 соединен с входами разрешения записи вторым входом группы первых регистров 5i (i=1, 2, …, m) и вторыми входами пятого 9 и девятого 13 регистров, выход третьей схемы сравнения 20m также подключен к четвертому входу синхронной установки в нулевое состояние триггера разрешения 2 и второму входу синхронной установки в единичное состояние триггера готовности результата 3, выход которого является первым выходом устройства 24, выходы группы из m первых 51, 52, …, 5m регистров являются группой из m вторых выходов 251, 252, …, 25m устройства, выходы пятого регистра 9 являются третьими выходами 26 устройства, выходы девятого регистра 13 являются четвертыми выходами устройства 27.
| RU 2009101397 A, 27.07.2010 | |||
| УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ СУБОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ И ЕГО ОЦЕНКИ | 2001 |
|
RU2193796C2 |
| Устройство для решения задач дискретного программирования | 1985 |
|
SU1298774A1 |
| US 7529768 B2, 05.05.2009. | |||
