0

What algorithm would pair parcels with a high proportion of property x to a parcel with a low proportion of property x so that the weighted average of the two parcels falls within an upper and lower bound? The algorithm needs to pair a set of parcels to maximise the quantity that fall into the given range. The parcels are of differing size.

For example, suppose I have a table of data that has tonnes of each block and percentage iron in each block. I can process two blocks at the same time to create an average iron percentage. I want to change the sequence of each block to maximise the tonnes that fall inside a percentage iron range.

  • 1
    Welcome to programmers.SE! Could you add some nontrivial, but short, example(s), including a situation where just pairing the max and min entries does not work? (I know they exist, but I’m not sure how deep the problems go.) – Christopher Creutzig Feb 4 '14 at 5:36
  • I don't know the answer but with these kinds of problems, I always prefer to start with a sorted set or list of the items. It's ALWAYS easier once it's sorted. – RibaldEddie Feb 4 '14 at 6:00
1

Create a list of all the parcels sort the list of parcels by weight.

Remove parcels from either the head or the tail of the list until the average weight falls within an acceptable range.

Pair each parcel at the head with a parcel at the tail, moving inwards, to get your pairs of parcels.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.