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

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

Реферат

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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