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

Формула изобретения

Устройство для решения задачи о рюкзаке, содержащее группу из m счетчиков 3₁ 3_m, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого соединен с пусковым входом устройства 19, а выход подсоединен к входу счетчика 3₁, группу из m вторых элементов И 4₁ 4_m, третий элемент И 16, четвертую группу элементов И 17, отличающееся тем, что в него дополнительно включены группы из m первых 5₁ 5_m, вторых 6₁ 6_m и третьих 8₁ 8_m регистров, m первых 7₁ 7_m и вторых 9₁ 9_m блоков умножения, первый 10 и второй 11 сумматоры, первая схема сравнения 12, четвертый регистр 13, вторая схема сравнения 14, пятый регистр 15, выход каждого счетчика 3 _i (i=1 m) подсоединен к первым входам группы элементов И 4 _i, к первому входу первого блока умножения 7_i и к первому входу второго блока умножения 9_i, второй вход блока умножения 9_i подсоединен к выходу третьего регистра 8_i, а выход - к одноименному входу первого сумматора 10, выход которого подсоединен к первому входу первой схемы сравнения 12, второй вход которой подсоединен к выходу четвертого регистра 13, а выход - к первому входу третьего элемента И 16, выход которого подсоединен к первому входу четвертой группы элементов И 17 и к вторым входам групп элементов И 4_i (i=1 m), выход каждой из которых подсоединен к входу первого регистра 5_i, выход каждого второго регистра 6 _i подсоединен ко второму входу первого блока умножения 7_i, выход которого подсоединен к одноименному входу второго сумматора 11, выход которого подсоединен к первому входу второй схемы сравнения 14, ко второму входу четвертой группы элементов И 17, выход которой подсоединен к входу пятого регистра 15, выход которого подсоединен ко второму входу второй схемы сравнения 14, выход которой подсоединен к ко второму входу элемента И 16, выход переполнения счетчика 3_i (i=1 m-1) подсоединен к входу счетчика 3_i+1, выход переполнения счетчика 3_m подключен к инверсному входу первого элемента И 2 и является выходом 18 устройства.

Описание изобретения к патенту

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

Наиболее близким по технической сущности является устройство [1], содержащее генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого соединен с пусковым входом устройства 19, а выход подсоединен к входу счетчика 3₁, группу из m вторых элементов И 4₁ 4_m, третий элемент И 16, четвертую группу элементов И 17.

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

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

Сущность изобретения состоит в том, что в устройство для решения задачи о рюкзаке, содержащее группу из m счетчиков 3₁ 3_m, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, второй вход которого соединен с пусковым входом устройства 19, а выход подсоединен к входу счетчика 3₁, группу из m вторых элементов И 4₁ 4_m, третий элемент И 16, четвертую группу элементов И 17, дополнительно включены группы из m первых 5₁ 5_m, вторых 6₁ 6_m и третьих 8₁ 8_m регистров, m первых 7₁ 7_m и вторых 9₁ 9_m блоков умножения, первый 10 и второй 11 сумматоры, первая схема сравнения 12, четвертый регистр 13, вторая схема сравнения 14, пятый регистр 15, выход каждого счетчика 3 _i (i=1 m) подсоединен к первым входам группы элементов И 4 _i, к первому входу первого блока умножения 7_i и к первому входу второго блока умножения 9_i, второй вход блока умножения 9_i подсоединен к выходу третьего регистра 8_i, а выход - к одноименному входу первого сумматора 10, выход которого подсоединен к первому входу первой схемы сравнения 12, второй вход которой подсоединен к выходу четвертого регистра 13, а выход - к первому входу третьего элемента И 16, выход которого подсоединен к первому входу четвертой группы элементов И 17 и к вторым входам групп элементов И 4_i (i=1 m), выход каждой из которых подсоединен к входу первого регистра 5_i, выход каждого второго регистра 6 _i подсоединен ко второму входу первого блока умножения 7_i, выход которого подсоединен к одноименному входу второго сумматора 11, выход которого подсоединен к первому входу второй схемы сравнения 14, ко второму входу четвертой группы элементов И 17, выход которой подсоединен к входу пятого регистра 15, выход которого подсоединен ко второму входу второй схемы сравнения 14, выход которой подсоединен ко второму входу элемента И 16, выход переполнения счетчика 3_i (i=1 m-1) подсоединен к входу счетчика 3_i+1, выход переполнения счетчика 3_m подключен к инверсному входу первого элемента И 2 и является выходом 18 устройства.

Проведенный поиск в известной научно-технической литературе не выявил наличие подобных технических решений.

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

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

Сущность изобретения поясняется чертежом. На чертеже представлена структурная схема предлагаемого устройства, где представлены генератор тактовых импульсов (ГТИ) 1, элемент И 2, счетчики 3_i (i=1 m, где m - число возможных различных предметов для помещения их в рюкзак), m вторых групп элементов И 4₁ 4_m, m первых 5₁ 5_m и вторых 6₁ 6_m регистров, m первых 7₁ 7_m блоков умножения, m третьих 8₁ 8_m регистров, m вторых 9₁ 9_m блоков умножения, первый сумматор 10, второй сумматор 11, первая схема сравнения 12, четвертый регистр 13, вторая схема сравнения 14, пятый регистр 15, третья группа элементов И 16, четвертая группа элементов И 17, выход 18 и вход 19 устройства.

Устройство работает следующим образом.

В исходном состоянии все счетчики 3_i (i=1 m, m - число предметов в рюкзаке) и регистры 5₁ 5_m устанавливаются в нулевое состояние.

На каждом регистре 6₁ 6_m хранится код стоимости единицы соответствующего предмета для помещения его в рюкзак. На каждом регистре 8 ₁ 8_m хранится код веса единицы предмета для рюкзака.

Выходы переполнения счетчиков 3_i (i=1 m-1) подсоединены к входам счетчиков 3_i+1, выход счетчика 3_m является выходом 18 устройства и одновременно подсоединен к инверсному входу элемента И 2.

Работа устройства начинается после подачи сигнала ПУСК на вход 19 устройства, после чего импульсы с выхода ГТИ 1 начинают поступать на вход счетчика 3₁.

Выход переполнения счетчика 3_i (i=1 m-1) подсоединен к входу счетчика 3_i+1. С выхода счетчика 3_i (i=1 m) код поступает на первые входы блоков умножения 7 _i и 9_i, на вторые входы которых поступают коды с выходов регистров 6_i и 8_i соответственно.

Код результата с выхода второго блока умножения 9 _i поступает на одноименный вход первого сумматора 10, с выхода которого суммарный код веса рюкзака для данного набора предметов поступает на первый вход второй схемы сравнения 12, на второй вход которой поступает код с выхода регистра 13 со значением допустимого веса рюкзака.

Одновременно код результата с выхода первого блока умножения 7_i поступает на одноименный вход второго сумматора 11, с выхода которого суммарный код стоимости набора предметов в рюкзаке поступает на второй вход четвертой группы элементов И 17 и на первый вход второй схемы сравнения 14, на второй вход которой поступает код с выхода регистра 15 со значением текущей стоимости набора предметов в рюкзаке.

Единичный сигнал на выходе первой схемы сравнения 12 появляется только в том случае, если код веса рюкзака на выходе сумматора 10 меньше или равен коду на выходе регистра 13 со значением допустимого веса рюкзака.

Единичный сигнал на выходе второй схемы сравнения 14 появляется только в том случае, если код стоимости набора предметов в рюкзаке на выходе второго сумматора 11 меньше или равен коду стоимости на выходе регистра 15 со значением текущей стоимости набора предметов в рюкзаке.

Сигналы с выходов схем сравнения 12 и 14 поступают на входы третьего элемента И 16, с выхода которого единичный сигнал (в случае всех единичных входных сигналов) поступает на первые входы группы элементов И 4_i (i=1 m) и на первый вход группы элементов И 17, на второй вход которой поступает код с выхода сумматора 11 для перезаписи его в регистр 15, куда записывается код максимальной стоимости набора предметов в рюкзаке.

Через открытые группы элементов И 4_i коды с выходов счетчиков 3j поступают на одноименные входы регистров 5_i, на которых фиксируются текущие значения количества предметов i-го типа в рюкзаке.

Сигналы с выходов переполнения счетчиков 3_i (i=1 m-1) поступают на входы счетчиков 3_i+1. Сигнал с выхода переполнения счетчика 3_m поступает на инверсный вход элемента И 2, в результате чего на выходе 18 устройства появляется сигнал окончания работы и прекращается подача импульсов с выхода ГТИ 1.

Результатом работы устройства являются:

коды на регистрах 5_i (i=1 m), на которых фиксируются коды чисел предметов i-го типа (i=1 m) в рюкзаке;

значение максимальной стоимости набора предметов в рюкзаке в регистре 15,

а также сигнал окончания работы 18 устройства.

Источники информации

1. Авторское свидетельство № 1383389, кл. G06F 15/20, 1987.