The task of the backpack: what's inside?
Honorable SergeyACTIVITI in his post told us about such a useful thing as a backpack problem, the solution of which was successfully implemented in the COIN-OR or GLPK solvers. And what's inside?
So, let us have a backpack of volume W, and a list of n things, each of which has a volume v [i] and a cost c [i], and each of which can be taken as many times as necessary. At the same time, all volumes and all costs will be positive and intact. How does the algorithm work?
Let's start an array of max length W + 1, in which, based on the results of the algorithm, we will get the greatest value that a set of things that can occupy a given volume can have - for each volume from 0 to W inclusive.
Or rather, after k iterations, we get for each volume i max [i] - the maximum possible cost of a set of things of volume i, which can contain only the first k things.
It is immediately clear that initially it is necessary to initialize max [0] = 0. What are the other elements of max? Without using any things, you can only get a weight gain of 0. So, in max [i] (0 <i <= W), you need to write something that will be worse than any possible cost of weight gain i. For example, -1.
After that you need to do n iterations.
')
At the kth iteration, we do the following.
Before iteration in the array, each element max [i] records the maximum possible cost of a set of things of weight i, which is composed of things 0..k-1. Each time, considering the element max [i], we will ensure that the maximum possible cost of a set of things of weight i, which is composed of things 0..k, was written there. To do this, check if there is a k-th thing in the optimal set, at least one? If not, then max [i] already contains the optimal cost. If there is, then, if you throw out one k-th thing from this set, then you will get the optimal set of things of volume iv [k], left out of things 0..k. But the latter is already recorded in max [iv [k]]! So, you just need to compare the values max [i] and max [iv [k]] + c [k] (if, of course, i> = v [k]). The maximum of them should be written in max [i].
So, after the k-th iteration, we will receive in each max [i] the highest value that a set of things can have, made up of things. So, after n iterations, we get exactly what was promised. It remains a matter of technology: go through the array max [i] and select the maximum element in it.
It is easy to see that the asymptotic behavior of the algorithm will be O (W * n), and the used memory - O (W).
Variations:
1. When you need to get not only the cost, but also the set itself .
In addition to the max array, we also write the prev array. In it we will write down what item we last put in the set. That is, if when comparing max [i] and max [iv [k]] + c [k] it turned out that max [iv [k]] + c [k] is better - this means that in the optimal weight gain i must be the kth subject. Thus, if we find out that the optimal value of max [i] is achieved when we set weight i, then we can write down what we added to the prev [i] thing. And go to the optimal set of weight i - v [prev [i]]. There, too, see what thing they took the last time. And so on, until we reach zero.
2. When each item can be taken only once .
It's still simpler: you just have to go through the array not from the bottom up, but from top to bottom in each iteration, that is, from W to 0. Then, if we consider max [iv [k]], it will still be recorded, the set What is the maximum cost of the weight i - v [k] that can be obtained using only things 0..k-1. Therefore, if it turns out that the k-th thing is to be used in the optimal set, then it will be used only once.
3. The choice of values as close as possible to this.
If there are no costs, then this algorithm obviously helps to fill the backpack as much as possible. Or, if we are not talking about a backpack, and it does not matter that the total volume of things is not more than the volume of a backpack, you can use a number to add a number that can be as close as possible to this one from several numbers.
In all cases, the asymptotic behavior of the operation time and the memory used is the same.
4. When each item can be taken a certain number of times.
For this variation, thanks lipstick .
There is a variation of the problem in which the thing with number i can be taken from 0 to q [i] times. Of course, you can “multiply” the i-th thing by q [i] units and solve the problem of a 0-1 backpack. However, the complexity of this solution will be O (W * ∑q [i]), which is not very good. In fact, you can go smarter.
Let q [i] = 1 + 2 + 4 + 8 +… + 2 ^ k + r [i], where r [i] <2 ^ (k + 1).
Then we will consider k + 2 objects with the volume 1 * v [i], 2 * v [i], ..., 2 ^ k * v [i], r [i] * v [i] and cost 1 * c [i ], 2 * c [i], ..., 2 ^ k * c [i], r [i] * c [i], respectively.
(“Names” of new items - “1st i-th thing”, “2 i-th items”, “4 i-th items”, etc.)
It is clear that by choosing different subsets of these k + 2 items, you can get any number (from 0 to q [i]) of type i items. That is, instead of “reproducing” things of the i-th type by q [i] units, we managed to limit ourselves to k + 2 = O (log q [i]) units.
Such a method will have complexity of order O (W * ∑log q [i]), which is much more efficient than a “naive” solution.
PS Who is not lazy, you can edit the article in Wikipedia - there is something wrong written =)
So, let us have a backpack of volume W, and a list of n things, each of which has a volume v [i] and a cost c [i], and each of which can be taken as many times as necessary. At the same time, all volumes and all costs will be positive and intact. How does the algorithm work?
Let's start an array of max length W + 1, in which, based on the results of the algorithm, we will get the greatest value that a set of things that can occupy a given volume can have - for each volume from 0 to W inclusive.
Or rather, after k iterations, we get for each volume i max [i] - the maximum possible cost of a set of things of volume i, which can contain only the first k things.
It is immediately clear that initially it is necessary to initialize max [0] = 0. What are the other elements of max? Without using any things, you can only get a weight gain of 0. So, in max [i] (0 <i <= W), you need to write something that will be worse than any possible cost of weight gain i. For example, -1.
After that you need to do n iterations.
')
At the kth iteration, we do the following.
Before iteration in the array, each element max [i] records the maximum possible cost of a set of things of weight i, which is composed of things 0..k-1. Each time, considering the element max [i], we will ensure that the maximum possible cost of a set of things of weight i, which is composed of things 0..k, was written there. To do this, check if there is a k-th thing in the optimal set, at least one? If not, then max [i] already contains the optimal cost. If there is, then, if you throw out one k-th thing from this set, then you will get the optimal set of things of volume iv [k], left out of things 0..k. But the latter is already recorded in max [iv [k]]! So, you just need to compare the values max [i] and max [iv [k]] + c [k] (if, of course, i> = v [k]). The maximum of them should be written in max [i].
So, after the k-th iteration, we will receive in each max [i] the highest value that a set of things can have, made up of things. So, after n iterations, we get exactly what was promised. It remains a matter of technology: go through the array max [i] and select the maximum element in it.
It is easy to see that the asymptotic behavior of the algorithm will be O (W * n), and the used memory - O (W).
Variations:
1. When you need to get not only the cost, but also the set itself .
In addition to the max array, we also write the prev array. In it we will write down what item we last put in the set. That is, if when comparing max [i] and max [iv [k]] + c [k] it turned out that max [iv [k]] + c [k] is better - this means that in the optimal weight gain i must be the kth subject. Thus, if we find out that the optimal value of max [i] is achieved when we set weight i, then we can write down what we added to the prev [i] thing. And go to the optimal set of weight i - v [prev [i]]. There, too, see what thing they took the last time. And so on, until we reach zero.
2. When each item can be taken only once .
It's still simpler: you just have to go through the array not from the bottom up, but from top to bottom in each iteration, that is, from W to 0. Then, if we consider max [iv [k]], it will still be recorded, the set What is the maximum cost of the weight i - v [k] that can be obtained using only things 0..k-1. Therefore, if it turns out that the k-th thing is to be used in the optimal set, then it will be used only once.
3. The choice of values as close as possible to this.
If there are no costs, then this algorithm obviously helps to fill the backpack as much as possible. Or, if we are not talking about a backpack, and it does not matter that the total volume of things is not more than the volume of a backpack, you can use a number to add a number that can be as close as possible to this one from several numbers.
In all cases, the asymptotic behavior of the operation time and the memory used is the same.
4. When each item can be taken a certain number of times.
For this variation, thanks lipstick .
There is a variation of the problem in which the thing with number i can be taken from 0 to q [i] times. Of course, you can “multiply” the i-th thing by q [i] units and solve the problem of a 0-1 backpack. However, the complexity of this solution will be O (W * ∑q [i]), which is not very good. In fact, you can go smarter.
Let q [i] = 1 + 2 + 4 + 8 +… + 2 ^ k + r [i], where r [i] <2 ^ (k + 1).
Then we will consider k + 2 objects with the volume 1 * v [i], 2 * v [i], ..., 2 ^ k * v [i], r [i] * v [i] and cost 1 * c [i ], 2 * c [i], ..., 2 ^ k * c [i], r [i] * c [i], respectively.
(“Names” of new items - “1st i-th thing”, “2 i-th items”, “4 i-th items”, etc.)
It is clear that by choosing different subsets of these k + 2 items, you can get any number (from 0 to q [i]) of type i items. That is, instead of “reproducing” things of the i-th type by q [i] units, we managed to limit ourselves to k + 2 = O (log q [i]) units.
Such a method will have complexity of order O (W * ∑log q [i]), which is much more efficient than a “naive” solution.
PS Who is not lazy, you can edit the article in Wikipedia - there is something wrong written =)
Source: https://habr.com/ru/post/93698/
All Articles