Looking for the best pair of items that don't exceed a certain weight?

Question

I have a set of objects, each of which has a weight and a value. I want to select a pair of objects with the highest total value, taking into account the limitation that their total weight does not exceed a certain threshold value. In addition, two arrays are assigned to me: one containing objects sorted by weight, and one containing objects sorted by value.

I know how to do this in O (n ² ), but how can I do this in O (n)?

Answer 1

Below is the solution O (n) , O (1).

Let object x be better than object y if and only if (x is not heavier than y) and (x is not less valuable) and (x is lighter or more valuable). Call the object x first-choice if the object is not better than x. There is an optimal solution consisting either of two objects of the first choice, or for the object of the first choice x and the object y, that only x is better than y.

The main tool is to be able to iterate over objects of the first choice from the lightest to the heaviest (= least valuable for the most valuable) and from the most valuable to the least valuable (= the heaviest and lightest). The iterator state is an index into objects by mass (respectively, value) and maximum value (respectively, minimum weight).

Each of the following steps: O (n).

• During scanning, every time we come across an object that is not the first choice, we know an object that is better than it. Scan once and view these pairs of objects.

• For each object of the first choice, from the lightest to the heaviest, determine the heaviest object of the first choice with which it can be paired, and consider a couple. (All lighter objects are less valuable.) As the last object becomes lighter over time, each iteration of the loop is depreciated by O (1). (See also search in a matrix whose rows and columns are sorted.)

---

Code for unbelievers. Not tested much.

from collections import namedtuple from operator import attrgetter Item = namedtuple('Item', ('weight', 'value')) sentinel = Item(float('inf'), float('-inf')) def firstchoicefrombyweight(byweight): bestsofar = sentinel for x in byweight: if x.value > bestsofar.value: bestsofar = x yield (x, bestsofar) def firstchoicefrombyvalue(byvalue): bestsofar = sentinel for x in byvalue: if x.weight < bestsofar.weight: bestsofar = x yield x def optimize(items, maxweight): byweight = sorted(items, key=attrgetter('weight')) byvalue = sorted(items, key=attrgetter('value'), reverse=True) maxvalue = float('-inf') try: i = firstchoicefrombyvalue(byvalue) y = i.next() for x, z in firstchoicefrombyweight(byweight): if z is not x and x.weight + z.weight <= maxweight: maxvalue = max(maxvalue, x.value + z.value) while x.weight + y.weight > maxweight: y = i.next() if y is x: break maxvalue = max(maxvalue, x.value + y.value) except StopIteration: pass return maxvalue items = [Item(1, 1), Item(2, 2), Item(3, 5), Item(3, 7), Item(5, 8)] for maxweight in xrange(3, 10): print maxweight, optimize(items, maxweight) 

Answer 2

This is a combinatorial optimization problem, and the fact that the values ​​are sorted means that you can easily try branching and snapping .

Answer 3

I think I have a solution that works in O (n log n) and O (n) extra space. This is not exactly the O (n) solution you wanted, but it is still better than a naive quadratic solution.

The intuition underlying the algorithm is that we want to be able to effectively determine for any amount of weight the maximum value that we can get with the help of one element that uses the maximum of this weight. If we can do this, we have a simple algorithm for solving the problem: iterating over an array of elements sorted by value. For each element, see How much additional value we could get by associating one element with it (using the values ​​that we previously calculated), then find which of these pairs is the maximum. If we can pre-process in O (n log n) and can answer each of the above requests in O (log n), then the total time for the second step will be O (n log n), and we have the answer.

The important note that we need to make for the pre-processing phase is as follows. Our goal is to create a structure that can answer the question "which element with a weight less than x has a maximum value?" Think about how we can do this by adding one item at a time. If we have an element (value, weight), and the structure is empty, then we want to say that the maximum value that we can get using weight no more than “weight” is “value”. This means that everything in the range [0, max_weight - weight) must be set to a value. Otherwise, suppose the structure is not empty when we try to add (value, weight). In this case, we want to say that any part of the range [0, weight], whose value is less than the value, must be replaced by a value.

The problem is that when we do these inserts, at different iterations k, O (k) different sub-ranges can be changed, which should lead to the O (n ² ) algorithm.However, we can use a very smart trick to avoid this. Suppose we insert all the elements in this data structure in descending order of value. In this case, when we add (value, weight), since we add elements in descending order of value, each existing value in the data structure must be higher than our value. This means that if the range [0, weight] completely crosses any range, these ranges will automatically exceed the value, so we do not need to update them. If we combine this with the fact that every range that we add always spans from zero to some value, the only part of the new range that can ever be added to the data structure is the range [weight, x), where x is the highest weight stored in the data structure so far.

To summarize, suppose we visit pairs (value, weight) in descending order of value, we can update our data structure as follows:

• If the structure is empty, note that the range [0, value] has the value "value".
• Otherwise, if the highest weight recorded in the structure is greater than the weight, skip this item.
• Otherwise, if the highest weight recorded so far is x, note that the range [weight, x] has a value of "value".

Please note that this means that we always separate the ranges at the beginning of the list of ranges that we have encountered so far. Because of this, we can think of saving the list of ranges as a simple array, where each element of the array tracks the top endpoint of a certain range and the value assigned to that range. For example, we could track ranges [0, 3), [3, 9) and [9, 12] as an array

 3, 9, 12 

If we then needed to split the range [0, 3) into [0, 1) and [1, 3), we could do this by adding 1 to it:

 1, 3, 9, 12 

If we represent this array in the reverse order (actually preserving the ranges from high to low, and not from low to high), this step of creating the array is done in O (n) time, because at each point we just do O (1) work over whether to add another element to the end of the array.

Once we have ranges stored in such a way as to determine which range includes a certain weight, we can simply use a binary search to find the largest element smaller than that weight. For example, to find 6 in the array above, we would do a binary search to find 3.

Finally, once we build this data structure, we can just look at each of the objects one at a time. For each element we see how much weight is left, use a binary search in another structure to see which element it should be paired with to maximize the total value, and then find the maximum achievable value.

Follow the example. Given a maximum allowable weight of 10 and objects

 Weight | Value ------+------ 2 | 3 6 | 5 4 | 7 7 | 8 

Let's see what the algorithm does. First, we need to create our supporting structure for ranges. We look at objects in descending order of value, starting with an object with a weight of 7 and a value of 8. This means that if we ever leave at least seven units of weight, we get 8 values. Now our array looks like this:

 Weight: 7 Value: 8 

Next, we consider an object with a weight of 4 and a value of 7. This means that with four or more units of weight on the left, we can get the value 7:

 Weight: 7 4 Value: 8 7 

Repeating this for the next element (weight six, value five) does not change the array, because if the object has weight six, if we ever have six or more units of free space, we will never choose this; we always accept the seven-digit element of weight four. We can say this because the table already has an object whose range includes the remaining weight of four.

Finally, we look at the last element (value 3, weight 2). This means that if we ever have the weight of two or more free ones, we can get 3 units of value. The final array now looks like this:

 Weight: 7 4 2 Value: 8 7 3 

Finally, we just look at the objects in any order to see which is the best option. When you look at an object with a weight of 2 and a value of 3, since the maximum allowable weight is 10, we need to indicate how much we can get a maximum of 10 - 2 = 8 weight. Binary array search tells us that this value is 8, so one option will give us 11 weight. If we look at an object with a weight of 6 and a value of 5, a binary search will tell us that with the five remaining weights we could get only 7 units of value, for a total of 12 values. Repeating this in the next two lines does not cause anything new, so the found optimal value has a value of 12, which is really the correct answer.

Hope this helps!

Answer 4

This looks like a backpack problem . I will use the naming from it ( num - weight, val - value).

The essential part:

• Start with a = 0 and b = n-1 . Assuming 0 is the index of the heaviest object, and n-1 is the index of the lightest object.
• The increase in a til of objects a and b satisfy the limit.
• Compare the current solution with the best solution.
• Decrease b by one.
• Go to 2.

Update:

This is a problem with the backpack, except for the limit of 2 items. You basically need to decide how much space you want for the first object and how much for another. There are n significant ways to split the available space, so the complexity is O(n) . The selection of the most valuable objects for placement in these places can be performed at no additional cost.