Below is an algorithm for the exact solution of the integer backpack problem. The proposed algorithm requires less computational resources and is perhaps somewhat simpler than the dynamic programming algorithm (DP).

The reason prompted the author to publish

The first version of the description of the algorithm was sent by me to the Institute of Mathematics. S. L. Sobolev of the Siberian Branch of the Russian Academy of Sciences, from where the answer was sent that this algorithm has been known for a long time. I quote:

One of his first mentions in the book of Kereller, Nemhauser, Ullman, Discrete, 15 p. 494-505, 1969.

Nevertheless, I decided to familiarize the community with the algorithm, since I did not find him in textbooks on discrete mathematics known to me (maybe I was looking bad). In the first version of the algorithm there was an error indicated to me by the user wataru . For this he thanks a lot. I tried to eliminate this error. I got to the algorithm on my own, so I hope I’m not violating anyone’s rights. Perhaps someone description will be interesting and useful.

Introduction

The one-dimensional backpack problem (0-1 knapsack) is a classic discrete optimization problem [1], [2]. This task and its variants are widely used for modeling a large number of practical problems. In general, the task can be formulated as follows: from a given set of objects with the properties “cost” and “weight”, it is required to select a certain number of objects in such a way as to obtain the maximum total cost while simultaneously observing the limit on the total weight.
More precisely, let P (i) > 0 and W (i) > 0, respectively, the cost and weight of the i -th item, where i = 1,2,3, ..., N , and N is the number of items.
It is required to find a Boolean vector X of dimension N , where
X (i) = 1 if item i is placed in a backpack;
X (i) = 0 if item i is not placed in the backpack;
that was the maximum sum Σ P (i) X (i)
and the inequality Σ W (i) X (i) ≤ C was fulfilled , where C > 0 is the capacity of the backpack.
There are various accurate and approximate algorithms for solving a backpack problem.
The exact algorithms include:

• brute force
• branch and bound method
• dynamic programming (DP)

.
The approximate algorithms are greedy (AJ) and genetic (GA). Comparison of various methods for solving a backpack problem is widely represented in the literature and on the Internet, so we will not dwell on it and get down to business right away. The proposed algorithm below can be conditionally viewed as a complication of LRA and as a simplification of the DP algorithm.
Consider a variant of the algorithm for solving the backpack problem, provided that the weights of objects are natural numbers, and the values ​​of objects are real numbers.

Description of the algorithm for solving a backpack problem with pseudocode elements

INPUT : // Input
Arrays of initial data (ID) contain integer weights W and real values P of items W (1 ... N) > 0 and P (1 ... N) > 0
where N is the number of items and C > 0 is the capacity of the backpack.
OUTPUT: // Output
A Boolean array X (1 ... N) , where X (i) = 1, if item with number i is included in the solution, and X (i) = 0, if item with number i is not included in the solution.

START // start of the algorithm
')
Stage 1 // Sort ID
Sort ID in order of decreasing the unit cost of items:
P (1) / W (1)> = P (2) / W (2)> = ...> = P (i) / W (i)> = ...> = P (N) / W (N)
where P (i) > 0 is the cost of item i , W (i) > 0 is the weight of item i .
In the array X (1 ... N) all elements are initially = 0.
To reduce the memory requirement for the algorithm, we determine the minimum weight in the set ID W_min = min (W)

Stage 2 // initialization of the working arrays
Create an array of real numbers LP of dimension (W_min ... C)
and an array of LCr integers of dimension (W_min ... C) . Fill in the array LP and LCr data of the first element from the sorted ID list

LP( W(1) ) = P(1) LCr( W(1) ) = 1 

where P (1) is the cost and W (1) is the weight of the first item in the sorted ID list.

Stage 3 // fill the working arrays

  FOR i = 2 TO N //      

Let W (i) and P (i) be the weight and cost of the current ID element.
Create an empty array of real Clone numbers of dimension (W_min ... C) .
Add the value of the current ID element to the Clone array.

 Clone( W(i) ) = P(i) 

.
We copy non-zero data from the LP array into the Clone array, adding the P (i) value of the current element and increasing its index by its weight W (i) , provided that the Clone index does not exceed the capacity of the backpack C.

 FOR j = W_min TO ( C - W(i) ) IF LP(j) >0 THEN Clone( j + W(i) ) = LP(j) + P(i) END IF NEXT //    

We carry out the modification of the arrays LP , LCr on the basis of the data of the array Clone . We update in the LP , LCr arrays only those elements whose cost in Clone is greater than in LP .

  FOR j = W_min TO C IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN LP( j ) = Clone( j ) LCr( j ) = i END IF NEXT //    LP, LCr NEXT //      

Stage 4 // formation of the result, reverse descent
In the LP array we find the maximum value of the cost Pmax = MAX (LP) , this is the cost of the optimal solution found. The index of the element found in the array is equal to the weight of the solution; we denote it by Wr , i.e. LP (Wr) = Pmax . Fill in the first found element in X:

  X( LCr( Wr ) ) = 1 

Further

 //    UNTIL Wr > 0 //  Wr = 0,   //          Wr = Wr - W( LCr( Wr ) ) // ,        X IF X(LCr( Wr ) = 0 then //   X( LCr( Wr ) ) = 1 //  ELSE //  

We leave UNTIL cycle and repeat stages 2 , 3 , 4 (only at stage 2 we do not create arrays LP, LCr , but fill them with zeros). Repeat step 1 (sorting ID) is not necessary. This is essentially a recursion, but due to the pre-sorting of the ID, it will not be deep. Some sets of recursion IDs may not exist at all. When repeating calculations, we consider only those IDs whose index is less than LCr (Wr) and reduce the required size of the backpack to the achieved weight Wr .

  N_NEW = LCr( Wr ) -1 C_NEW = Wr GOTO  2 END IF NEXT //     

FINISH // end of algorithm
The cost of the found solution is Σ P (i) X (i) , the weight is Σ W (i) X (i) .
The correctness of the calculation of the final cost of a backpack is easily proved by induction. Restoration of the optimal set of objects is also not difficult. The presented algorithm allows to obtain an exact solution of the integer backpack problem.

Summary notes

1. The overall complexity of the presented algorithm is the sum of the complexity of sorting the ID and the complexity of performing stage 3 of the algorithm (taking into account the number of iterations). The operation time of stage 3 is proportional to the number of items per backpack capacity ( N * C ). Predetermining the number of iterations is quite difficult. The number of iterations can vary from 0 to the number of items in the solution Σ X (i) . At each iteration occurring at stage 4, the amount of calculations at stages 2, 3 decreases. The upper estimate of the time complexity of the entire algorithm does not exceed N * C * (number of iterations + 1)
2. The algorithm's need for memory is proportional to the capacity of the backpack C and does not depend on the number of objects in the input data set N , which favorably distinguishes it from the DP method.
3. The internal cycles of step 3 are easily performed in parallel.
4. With a large variation in the unit cost of items, if at stage 3 of the algorithm changes in the upper part of the LP array cease to occur, you can interrupt step 3 and not consider the remaining items with a low unit cost.
5. If the capacity of the backpack C is large enough so that arrays of dimension C cannot be created for technical reasons or the weights of the objects are real numbers, then the proposed algorithm can be easily modified by replacing the arrays with linked lists.
6. Is this algorithm polynomial or not, I do not presume to judge.

Literature

1. Papadimitriu H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. M .: Mir, 1985.
2. T. Cormen, C. Lazerson, R. Rivest, K. Stein. Algorithms: construction and analysis. M .: Publishing house "Williams", 2005.