RU2413287C2 - Knapsack problem solving apparatus - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: knapsack problem solving apparatus having a group of m counters 3₁…3_m, a clock pulse generator 1, a first AND element 2, a group of m second AND elements 4₁…4_m, a third AND element 16, a fourth group of AND elements 17, also has a group of m first 5₁…5_m, second 6₁…6_m and third 8₁…8_m registers, m first 7₁…7_m and second 9₁…9_m multiplier units, a first 10 and a second 11 adder, a first comparator 12, a fourth register 13, a second comparator 14 and a fifth register 15.

EFFECT: possibility of simulating the process of filling a knapsack with different objects so that the total cost of the filled knapsack is maximum for limited total weight of the entire knapsack.

1 dwg

Description

The invention relates to computer technology and is intended to simulate the process of filling a backpack (container, barge, transport aircraft, etc.) with various objects so that the total cost of a filled backpack would be maximum while limiting the total weight of the entire backpack.

The closest in technical essence is the device [1], containing a clock pulse generator (GTI) 1, the output of which is connected to the first input of the first element And 2, the second input of which is connected to the start input of the device 19, and the output is connected to the input of the counter 3 ₁ , a group of m second elements And 4 ₁ ... 4 _m , the third element And 16, the fourth group of elements And 17.

The disadvantage of this device is the inability to simulate the process of filling the backpack (container, barge, transport aircraft, etc.) with various objects so that the total cost of the filled backpack would be maximum while limiting the total weight of the entire backpack.

The objective of the invention is to create a device that allows simulating the process of filling a backpack (container, barge, transport aircraft, etc.) with various objects so that the total cost of a filled backpack would be maximum while limiting the total weight of the entire backpack.

The essence of the invention lies in the fact that the device for solving the backpack problem, containing a group of m counters 3 ₁ ... 3 _m , a clock pulse generator (GTI) 1, the output of which is connected to the first input of the first element And 2, the second input of which is connected to the starting input of the device 19, and the output is connected to the input of the counter 3 ₁ , a group of m second elements And 4 ₁ ... 4 _m , a third element And 16, a fourth group of elements And 17, additionally included groups of m first 5 ₁ ... 5 _m , second 6 ₁ ... 6 _m and third 8 ₁ ... 8 _m registers, m first 7 ₁ ... 7 _m and second 9 ₁ ... 9 _m multiplication blocks, the first 10 and second 11 adders, the first comparison circuit 12, the fourth register 13, the second comparison circuit 14, the fifth register 15, the output of each counter 3 _i (i = 1 ... m) is connected to the first inputs of the group of elements And 4 _i , to the first input the first block of multiplication 7 _i and to the first input of the second block of multiplication 9 _i , the second input of the block of multiplication 9 _{i is} connected to the output of the third register 8 _i , and the output is connected to the same input of the first adder 10, the output of which is connected to the first input of the first comparison circuit 12, the second input of which is connected to the output of the fourth register 13 and the output is to the first input of the third element And 16, the output of which is connected to the first input of the fourth group of elements And 17 and to the second inputs of the groups of elements And 4 _i (i = 1 ... m), the output of each of which is connected to the input of the first register 5 _i , the output of each second register 6 _{i is} connected to the second input of the first block of multiplication 7 _i , the output of which is connected to the same input of the second adder 11, the output of which is connected to the first input of the second comparison circuit 14, to the second input of the fourth group of elements And 17, the output of which connected to input p the bright register 15, the output of which is connected to the second input of the second comparison circuit 14, the output of which is connected to the second input of the And 16 element, the overflow output of the counter 3 _i (i = 1 ... m-1) is connected to the input of the counter 3 _{i + 1} , the overflow output the counter 3 _{m is} connected to the inverse input of the first element And 2 and is the output 18 of the device.

A search in the well-known scientific and technical literature did not reveal the presence of such technical solutions.

The novelty of the proposed device is that the new technical device differs from the prototype in that it additionally introduces groups of m first 5 ₁ ... 5 _m , second 6 ₁ ... 6 _m and third 8 ₁ ... 8 _m registers, m first 7 ₁ ... 7 _m and second 9 ₁ ... 9 _m multiplication blocks, the first 10 and second 11 adders, the first comparison circuit 12, the fourth register 13, the second comparison circuit 14, the fifth register 15, the output of each counter 3 _i (i = 1 ... m) connected to the first inputs of the group of elements And 4 _i , to the first input of the first block of multiplication 7 _i and to the first input of the second block of multiplication 9 _i , the second input of the multiplication unit 9 _{i is} connected to the output of the third register 8 _i , and the output is connected to the same input of the first adder 10, the output of which is connected to the first input of the first comparison circuit 12, the second input of which is connected to the output of the fourth register 13, and the output - to the first input of the third element And 16, the output of which is connected to the first input of the fourth group of elements And 17 and to the second inputs of the groups of elements And 4 _i (i = 1 ... m), the output of each of which is connected to the input of the first register 5 _i , output each second register 6 is connected to the second _i th input of the first multiplier 7 _i, the output of which is connected to the same name input of the second adder 11, whose output is connected to the first input of the second comparison circuit 14, to the second input of the fourth group of AND gates 17, whose output is connected to the input of the fifth register 15, whose output is connected to the second input of the second comparison circuit 14, the output of which is connected to the second input of the And 16 element, the overflow output of the counter 3 _i (i = 1 ... m-1) is connected to the input of the counter 3 _{i + 1} , the overflow output of the counter 3 _{m is} connected to the inverse input the first And lementa 2 and 18 is an output device.

An inventive step is achieved in that the introduction of the corresponding elements into a known prototype together with the connections allows us to solve a new technical problem, the solution of which is not currently reflected in well-known computers and in the literature. The proposed device allows you to quickly determine the optimal filling of the backpack (container, barge, transport aircraft, etc.) with various objects so that the total cost of the filled backpack would be maximum while limiting the total weight of the entire backpack.

The invention is illustrated in the drawing. The drawing shows a structural diagram of the proposed device, which shows a clock pulse generator (GTI) 1, element And 2, counters 3 _i (i = 1 ... m, where m is the number of possible different items to put them in a backpack), m second groups of elements And 4 ₁ ... 4 _m , m first 5 ₁ ... 5 _m and second 6 ₁ ... 6 _m registers, m first 7 ₁ ... 7 _m multiplication blocks, m third 8 ₁ ... 8 _m registers, m second 9 ₁ ... 9 _m blocks multiplication, the first adder 10, the second adder 11, the first comparison circuit 12, the fourth register 13, the second comparison circuit 14, the fifth register 15, the third group of elements And 16, the fourth melting the group of AND gates 17, outlet 18 and inlet 19 of the device.

The device operates as follows.

In the initial state, all the counters 3 _i (i = 1 ... m, m is the number of items in the backpack) and the registers 5 ₁ ... 5 _m are set to zero.

Each register 6 ₁ ... 6 _m stores the unit cost code of the corresponding item for placing it in a backpack. Each register 8 ₁ ... 8 _m stores the code of the unit weight of the item for the backpack.

The overflow outputs of the counters 3 _i (i = 1 ... m-1) are connected to the inputs of the counters 3 _{i + 1} , the output of the counter 3 _m is the output 18 of the device and is simultaneously connected to the inverse input of the And 2 element.

The operation of the device begins after applying the START signal to the input 19 of the device, after which the pulses from the output of the GTI 1 begin to flow to the input of the counter 3 ₁ .

The counter overflow output 3 _i (i = 1 ... m-1) is connected to the input of the counter 3 _{i + 1} . From the output of the counter 3 _i (i = 1 ... m), the code enters the first inputs of the multiplication blocks 7 _i and 9 _i , the second inputs of which receive codes from the outputs of the registers 6 _i and 8 _i, respectively.

The result code from the output of the second multiplication block 9 _i goes to the input of the same adder 10 of the same name, from the output of which the total backpack weight code for this set of items goes to the first input of the second comparison circuit 12, the second input of which receives the code from the output of register 13 with a value of valid backpack weights.

At the same time, the result code from the output of the first multiplication unit 7 _i goes to the input of the second adder 11 of the same name, from the output of which the total cost code of a set of items in the backpack goes to the second input of the fourth group of elements And 17 and to the first input of the second comparison circuit 14, to the second input of which a code arrives from the output of register 15 with the value of the current value of a set of items in a backpack.

A single signal at the output of the first comparison circuit 12 appears only if the backpack weight code at the output of the adder 10 is less than or equal to the code at the output of the register 13 with the value of the allowable backpack weight.

A single signal at the output of the second comparison circuit 14 appears only if the code for the cost of a set of items in a backpack at the output of the second adder 11 is less than or equal to the value code at the output of register 15 with the value of the current cost of a set of items in a backpack.

The signals from the outputs of the comparison circuits 12 and 14 are fed to the inputs of the third element And 16, the output of which a single signal (in the case of all single input signals) is fed to the first inputs of the group of elements And 4 _i (i = 1 ... m) and to the first input of the group elements And 17, the second input of which receives the code from the output of the adder 11 to overwrite it in register 15, where the code is written the maximum cost of a set of items in a backpack.

Through the open groups of elements And 4 _{i, the} codes from the outputs of the counters 3j go to the inputs of the same register 5 _i , on which the current values of the number of items of the i-type in the backpack are fixed.

The signals from the outputs of the overflow counters 3 _i (i = 1 ... m-1) are fed to the inputs of the counters 3 _{i + 1} . The signal from the counter overflow output 3 _m goes to the inverse input of the And 2 element, as a result of which the output signal 18 appears at the device output 18 and the pulse supply from the GTI output 1 stops.

The result of the device are:

codes on registers 5 _i (i = 1 ... m), on which codes of numbers of objects of the i-th type (i = 1 ... m) in the backpack are fixed;

the value of the maximum cost of a set of items in a backpack in register 15,

as well as the end signal 18 of the device.

Information sources

1. Copyright certificate No. 1383389, cl. G06F 15/20, 1987.

Claims (1)

A device for solving the backpack problem, containing a group of m counters 3 ₁ ... 3 _m , a clock pulse generator (GTI) 1, the output of which is connected to the first input of the first element And 2, the second input of which is connected to the start input of the device 19, and the output is connected to the counter input 3 ₁ , a group of m second elements And 4 ₁ ... 4 _m , a third element And 16, a fourth group of elements And 17, characterized in that it additionally includes groups of m first 5 ₁ ... 5 _m , second 6 ₁ ... 6 _m and third 8 ₁ ... 8 _m registers, m first 7 ₁ ... 7 _m and second 9 ₁ ... 9 _m multiplication blocks, the first 10 and T Ora 11 adders, the first comparison circuit 12, the fourth register 13, the second comparison circuit 14, the fifth register 15, the output of each counter 3 _i (i = 1 ... m) is connected to the first inputs of the group of elements And 4 _i , to the first input of the first multiplication block 7 _i and to the first input of the second multiplication unit 9 _i , the second input of the multiplication unit 9 _{i is} connected to the output of the third register 8 _i , and the output is connected to the same input of the first adder 10, the output of which is connected to the first input of the first comparison circuit 12, the second input of which connected to the output of the fourth register 13, and the output to p moat input of the third AND gate 16, whose output is connected to the first input of the fourth group of AND gates 17 and to the second inputs of the groups of AND gates 4 _{i (i} = 1 ... m), the output of each of which is connected to the input of the first register 5 _i, the output of each of the second register 6 _i connected to the second input of the first multiplier 7 _i, the output of which is connected to the same name input of the second adder 11, whose output is connected to the first input of the second comparison circuit 14, to the second input of the fourth group of AND gates 17, whose output is connected to the input of the fifth registers of and 15, whose output is connected to the second input of the second comparison circuit 14 whose output is connected to the second input of AND gate 16, the overflow output of the counter 3 _{i (i} = 1 ... m-1) is connected to the input of the counter 3, _{i + 1,} the overflow outlet the counter 3 _{m is} connected to the inverse input of the first element And 2 and is the output 18 of the device.