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

Авторы патента:

 


Владельцы патента RU 2413287:

Негосударственное образовательное учреждение высшего профессионального образования Московский институт предпринимательства и права (RU)

Изобретение относится к области вычислительной техники. Технический результат заключается в обеспечении возможности моделирования процесса заполнения рюкзака (контейнера, баржи, транспортного самолета и т.д.) различными предметами таким образом, чтобы суммарная стоимость заполненного рюкзака была бы максимальной при ограничении на суммарный вес всего рюкзака. Такой результат достигается благодаря тому, что в устройство для решения задачи о рюкзаке, содержащее группу из m счетчиков 31…3m, генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, группу из m вторых элементов И 41…4m, третий элемент И 16, четвертую группу элементов И 17, дополнительно включены группы из m первых 51…5m, вторых 61…6m и третьих 8i…8m регистров, m первых 71…7m и вторых 91…9m блоков умножения, первый 10 и второй 11 сумматоры, первая схема сравнения 12, четвертый регистр 13, вторая схема сравнения 14, пятый регистр 15. 1 ил.

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



 

Похожие патенты:

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

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

Изобретение относится к области электронных цифровых вычислительных машин. .

Изобретение относится к средствам для обучения математике, в частности решения алгебраических и неопределенных уравнений. .

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

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

Изобретение относится к комплексам, предназначенным для обеспечения проведения подвижных игр. .

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

Изобретение относится к области вычислительной техники и может найти применение в вычислительных системах с параллельной обработкой информации и высоким быстродействием.

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

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

Изобретение относится к вычислительной технике. .

Изобретение относится к системе и способу для использования рукописного ввода при вводе с использованием списка автоматического заполнения. .

Изобретение относится к области информационных технологий, в частности к платформе хранения информации. .

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

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

Изобретение относится к устройствам и способам обработки информации. .

Изобретение относится к сетевой системе. .

Изобретение относится к области криминалистики и судебной экспертизы
Наверх