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

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

 

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

Техническим результатом является повышение быстродействия известного устройства [1] за счет осуществления упорядоченного перебора вариантов заполнения рюкзака.

Технический результат достигается тем, что в известное устройство [1], содержащее группу из m счетчиков 31…3m, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, информационный выход счетчика 3i (i=1…m) подсоединен к первым входам первого 11i и второго 12i блоков умножения и к первому входу группы вторых элементов И 7i, выход которого подсоединен к входу первого регистра 9i, выход которого является первым выходом 28i устройства, выход второго регистра 10i подсоединен к второму входу первого блока умножения 11i, выход которого подсоединен к одноименному входу первого сумматора 13, выход которого подсоединен к первому входу первой схемы сравнения 16 и к первому входу группы третьих элементов И 17, выход которого подсоединен к входу третьего регистра 20, выход которого подсоединен к второму входу первой схемы сравнения 16 и является выходом 29 устройства, выход первой схемы сравнения 16 подсоединен к первому входу четвертого элемента И 19, выход которого подсоединен к второму входу группы третьих элементов И 17 и к вторым входам вторых элементов И 7i (i=1…m), выход четвертого регистра 8i (i=1…m) подсоединен ко второму входу второго блока умножения 12i, выход которого подсоединен к одноименному входу второго сумматора 14, выход которого подсоединен к первому входу второй схемы сравнения 15, второй вход которой подсоединен к выходу пятого регистра 18, а выход подсоединен ко второму входу четвертого элемента И 19, выход каждого из группы шестых регистров 25i…25m подсоединен к первому входу группы пятых элементов И 23i, второй вход которых подсоединен к выходу первого элемента ИЛИ 24i, второй вход которого подсоединен к пусковому входу устройства 26, вход элемента задержки 22 подсоединен к пусковому входу устройства 26, а выход - к первому входу триггера 21, выход которого подсоединен к второму входу первого элемента И 2, выход каждого пятого элемента И 23i (i=1…m) подсоединен к второму входу одноименного счетчика 3i.

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

Задача изобретения - создать устройство, обеспечивающее повышенное быстродействие.

Сущность изобретения состоит в том, что в известное устройство для решения задачи о рюкзаке, содержащее группу из m счетчиков 31…3m, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, информационный выход счетчика 3i (i=1…m) подсоединен к первым входам первого 11i и второго 12i блоков умножения и к первому входу группы вторых элементов И 7i, выход которого подсоединен к входу первого регистра 9i, выход которого является первым выходом 28i устройства, выход второго регистра 10i подсоединен к второму входу первого блока умножения 11i, выход которого подсоединен к одноименному входу первого сумматора 13, выход которого подсоединен к первому входу первой схемы сравнения 16 и к первому входу группы третьих элементов И 17, выход которого подсоединен к входу третьего регистра 20, выход которого подсоединен к второму входу первой схемы сравнения 16 и является выходом 29 устройства, выход первой схемы сравнения 16 подсоединен к первому входу четвертого элемента И 19, выход которого подсоединен к второму входу группы третьих элементов И 17 и к вторым входам вторых элементов И 7i (i=1…m), выход четвертого регистра 8i (i=1…m) подсоединен ко второму входу второго блока умножения 12i, выход которого подсоединен к одноименному входу второго сумматора 14, выход которого подсоединен к первому входу второй схемы сравнения 15, второй вход которой подсоединен к выходу пятого регистра 18, а выход подсоединен ко второму входу четвертого элемента И 19, выход каждого из группы шестых регистров 251…25m подсоединен к первому входу группы пятых элементов И 23i, второй вход которых подсоединен к выходу первого элемента ИЛИ 24i, второй вход которого подсоединен к пусковому входу устройства 26, вход элемента задержки 22 подсоединен к пусковому входу устройства 26, а выход - к первому входу триггера 21, выход которого подсоединен к второму входу первого элемента И 2, выход каждого пятого элемента И 23i (i=1…m) подсоединен к второму входу одноименного счетчика 3i, включены группы вторых элементов ИЛИ 41…4m, группа третьих схем сравнения 51…5m, группа седьмых регистров 61…6m, выход каждого седьмого регистра 6i подсоединен к первому входу третьей схемы сравнения 5i, второй вход которой подсоединен к выходу одноименного счетчика 3i, а выход - к первому входу одноименного второго элемента ИЛИ 4i, второй вход которого подсоединен к выходу переполнения счетчика 3i, выход каждого второго элемента ИЛИ 4i (i=1, …(m-1)) подсоединен к счетному входу счетчика 3i+1 и к второму входу одноименного первого элемента ИЛИ 24i, выход второго элемента ИЛИ 4m подсоединен к второму входу триггера 21, к второму входу одноименного первого элемента ИЛИ 24m и к выходу 27 устройства.

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

Новизна предлагаемого устройства заключается в том, что новое техническое устройство отличается от прототипа тем, что дополнительно в него введены группы вторых элементов ИЛИ 41…4m, группа третьих схем сравнения 51…5m, группа седьмых регистров 61…6m, выход каждого седьмого регистра 6i подсоединен к первому входу третьей схемы сравнения 5i, второй вход которой подсоединен к выходу одноименного счетчика 3i, а выход - к первому входу одноименного второго элемента ИЛИ 4i, второй вход которого подсоединен к выходу переполнения счетчика 3i, выход каждого второго элемента ИЛИ 4i (i=1, …(m-1)) подсоединен к счетному входу счетчика 3i+1 и к второму входу одноименного первого элемента ИЛИ 24i, выход второго элемента ИЛИ 4m подсоединен к второму входу триггера 21, к второму входу одноименного первого элемента ИЛИ 24m и к выходу 27 устройства.

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

Сущность изобретения поясняется чертежом. На чертеже (фиг.1) представлена структурная схема предлагаемого устройства, где на фиг.1 представлены генератор тактовых импульсов (ГТИ) 1, первый элемент И 2, счетчики 3i, m, где m - число возможных различных предметов для помещения их в рюкзак), m групп элементов ИЛИ 41…4m, m схем сравнения 51…5m, m регистров 61…6m, m групп элементов И 71…7m, m регистров 81…8m, m регистров 91…9m, m регистров 101…10m, m блоков умножения 111…11m, m блоков умножения 121…12m, сумматор 13, сумматор 14, схема сравнения 15, схема сравнения 16, группа элементов И 17, регистр 18, элемент И 19, регистр 20, триггер 21, элемент задержки 22, группы из элементов И 231…23m, m элементов ИЛИ 241…24m, группа регистров 251…25m, пусковой вход устройства 26, выход 27 устройства, выходы 281…28m и выход 29 устройства.

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

В исходном состоянии триггер 21, регистр 20, все счетчики 3i (i=1…m, m - число предметов в рюкзаке) и регистры 91…9m устанавливаются в нулевое состояние. На регистре 18 хранится код допустимого веса рюкзака. На каждом регистре 101…10m хранится код стоимости единицы соответствующего предмета для помещения его в рюкзак. На каждом регистре 81…8m хранится код веса единицы предмета для рюкзака.

На регистрах 25i (i=1…m) хранятся коды чисел нижних границ предметов в рюкзаке (обязательных для помещения их в рюкзак некоторого числа разных предметов, например, для туриста в рюкзаке обязательно должны быть не менее двух пачек сухарей, одной пачки сахара и т.д.). На регистрах 6i (i=1…m) хранятся коды чисел верхних границ предметов в рюкзаке (достаточных для помещения их в рюкзак некоторого числа разных предметов, например, для туриста в рюкзаке обязательно должны быть не более двух пачек тушенки, трех пачек сухарей и т.д.).

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

Работа устройства начинается после подачи сигнала ПУСК на вход 26 устройства. После подачи сигнала ПУСК содержимое регистров 25i (i=1…m) через открытые элементы И 23i записываются в счетчики 3i (1=1…m), так как пусковой сигнал через элемент ИЛИ 24i поступает на установочный вход элемента И 23i.

Пусковой сигнал через элемент задержки 22 (задержка осуществляется на время перезаписи содержимого регистров 25i (i=1…m) через открытые элементы И 23i в счетчики 3;) устанавливает триггер 21 в единичное, состояние, после чего импульсы с выхода ГТИ 1 начинают поступать через открытый элемент И 2 на вход счетчика 31.

Выход переполнения счетчика 3i (i=1…m-1) через элемент ИЛИ 4i подсоединен к входу счетчика 3i+1. С выхода счетчика 3i (i=1…m) код поступает на первые входы блоков умножения 11i и 12i, на вторые входы которых поступают коды с выходов регистров 10i и 8i соответственно.

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

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

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

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

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

Через открытые группы элементов И 7i коды с выходов счетчиков 3i поступают на входы регистров 9i, на которых фиксируются текущие значения количества предметов i-го типа (i=1…m) в рюкзаке и их значения могут быть сняты с выходов 28i.

Одновременно коды с выходов счетчиков 3i поступают на первые входы схем сравнения 5i, на вторые входы которых поступают коды максимальных значений количества предметов с выхода регистра 6i. В случае, если код на регистре 6i превосходит значение на счетчике 3i, то на выходе схемы 5i единичный сигнал поступает также на другой вход элемента ИЛИ 4i.

Сигналы с выходов переполнения счетчиков 3i (i=1…m-1) поступают через элементы ИЛИ 4i на входы счетчиков 3i+1. Кроме того, сигнал переполнения с выхода счетчика 3i (i=1…m) через элемент ИЛИ 24i (i=1…m) обеспечивает перезапись кода с выхода регистра 25i через открытые элементы И 23i в счетчики 3i.

Сигнал с выхода переполнения счетчика 3m поступает на установочный в нулевое состояние вход триггера 21, тем самым закрывается элемент И 2, а на выходе 27 устройства появляется сигнал окончания работы, после чего прекращается подача импульсов с выхода ГТИ 1.

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

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

значение максимальной стоимости набора предметов в рюкзаке в регистре 20 и снимается с выхода 29;

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

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

Использованные источники

1. Патент №2443013, кл. G06F 17/00, 2012.

Устройство для решения задачи о рюкзаке, содержащее группу из m счетчиков 31…3m, генератор тактовых импульсов (ГТИ) 1, выход которого соединен с первым входом первого элемента И 2, выход которого соединен с входом счетчика 31, информационный выход счетчика 3i (i=1…m) подсоединен к первым входам первого 11i и второго 12i блоков умножения и к первому входу группы вторых элементов И 7i, выход которого подсоединен к входу первого регистра 9i, выход которого является первым выходом 28i устройства, выход второго регистра 10i подсоединен к второму входу первого блока умножения 11i, выход которого подсоединен к одноименному входу первого сумматора 13, выход которого подсоединен к первому входу первой схемы сравнения 16 и к первому входу группы третьих элементов И 17, выход которого подсоединен к входу третьего регистра 20, выход которого подсоединен к второму входу первой схемы сравнения 16 и является выходом 29 устройства, выход первой схемы сравнения 16 подсоединен к первому входу четвертого элемента И 19, выход которого подсоединен к второму входу группы третьих элементов И 17 и к вторым входам вторых элементов И 7i (i=1…m), выход четвертого регистра 8i (i=1…m) подсоединен ко второму входу второго блока умножения 12i, выход которого подсоединен к одноименному входу второго сумматора 14, выход которого подсоединен к первому входу второй схемы сравнения 15, второй вход которой подсоединен к выходу пятого регистра 18, а выход подсоединен ко второму входу четвертого элемента И 19, выход каждого из группы шестых регистров 251…25m подсоединен к первому входу группы пятых элементов И 23i, второй вход которых подсоединен к выходу первого элемента ИЛИ 24i, второй вход которого подсоединен к пусковому входу устройства 26, вход элемента задержки 22 подсоединен к пусковому входу устройства 26, а выход - к первому входу триггера 21, выход которого подсоединен к второму входу первого элемента И 2, выход каждого пятого элемента И 23i (i=1…m) подсоединен к второму входу одноименного счетчика 3i, отличающееся тем, что в него дополнительно включены группы вторых элементов ИЛИ 41…4m, группа третьих схем сравнения 51…5m, группа седьмых регистров 61…6m, выход каждого седьмого регистра 6i подсоединен к первому входу третьей схемы сравнения 5i, второй вход которой подсоединен к выходу одноименного счетчика 3i, а выход - к первому входу одноименного второго элемента ИЛИ 4i, второй вход которого подсоединен к выходу переполнения счетчика 3i, выход каждого второго элемента ИЛИ 4i (i=1, …(m-1)) подсоединен к счетному входу счетчика 3i+1 и к второму входу одноименного первого элемента ИЛИ 24i, выход второго элемента ИЛИ 4m подсоединен к второму входу триггера 21, к второму входу одноименного первого элемента ИЛИ 24m и к выходу 27 устройства.



 

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

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

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

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

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

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

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

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

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

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

Изобретение относится к сетевым вычислительным системам. Техническим результатом является повышение эффективности обработки данных за счет использования обучающих данных.

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

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

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

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

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

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

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

Изобретение относится к области оценки компьютерных ресурсов компьютерной сети по объектам интереса с учетом требований к компьютерным системам, на которых располагаются компьютерные ресурсы, и требований к объектам интереса как к содержимому компьютерных ресурсов. Технический результат настоящего изобретения заключается в обеспечении возможности определения компьютерных ресурсов в рамках компьютерной сети, подходящих для целей, заданных выбранными требованиями. Способ определения компьютерных ресурсов в компьютерной сети содержит этапы, на которых: а) формируют с помощью средства инвентаризации компьютерной сети список компьютерных ресурсов, находящихся на компьютерных системах, удовлетворяющих требованиям к компьютерным системам; где компьютерная сеть состоит, по меньшей мере, из двух компьютерных систем; где требования к компьютерным системам хранятся в базе данных требований к компьютерным системам средства хранения требований; б) собирают с помощью средства инвентаризации компьютерной сети информацию обо всех объектах интереса, имеющихся на компьютерных ресурсах из упомянутого списка компьютерных ресурсов; где компьютерный ресурс содержит в себе, по меньшей мере, один объект интереса; где объектами интереса являются файлы и программное обеспечение; в) анализируют с помощью средства анализа данных собранную информацию для определения объектов интереса, удовлетворяющих требованиям к объектам интереса; где требования к объектам интереса хранятся в базе данных требований к объектам интереса средства хранения требований; г) оценивают с помощью средства оценки компьютерных ресурсов каждый компьютерный ресурс из списка компьютерных ресурсов по количеству объектов интереса, удовлетворяющих требованиям к объектам интереса; д) определяют с помощью средства оценки компьютерных ресурсов, по меньшей мере один компьютерный ресурс, имеющий наивысшую оценку среди всех компьютерных ресурсов в рамках компьютерной сети, по результатам оценки, выполненным на этапе г). 2 н. и 11 з.п. ф-лы, 4 ил.

Изобретение относится к средствам управления счетом оплаты абонентских услуг. Технический результат заключается в в повышении безопасности платежа. Система содержит: клиентское устройство, приемопередатчик, логику, сконфигурированную для создания, по меньшей мере, одного первичного счета, при этом, по меньшей мере, один первичный счет представляет периодические платы, которые начисляются на счет оплаты абонентских услуг на периодической основе; и логику, сконфигурированную для создания, по меньшей мере, одного вторичного счета, при этом, по меньшей мере один вторичный счет представляет сумму предоплаченной услуги, которая действительна для счета оплаты абонентских услуг. 2 н. и 10 з.п. ф-лы, 5 ил.
Наверх