Algorithm for re-arranging a sequence of weights

Question

I have a number of items in an array, each one associated to a certain weight. There is a business rule saying that no two adjacent items cannot have a total weight of more than a certain value, let's say 100 for simplicity.

For example, the following is OK:

[40,60,40,50]

But not this one (since 50+60 = 110)

[50,60,40] 

I am trying to implement an algorithm that will rearrange the items (if possible) so that the business rule is fulfilled. For example, the second one could be rearranged to [60,40,50] or [50,40,60]

The algorithm should also tres to minimize the number of moved items, i.e. the first solution above is most appropriate since the "sub permutation" [60,40] is maintained.

I'm not looking for a complete answer or code examples, but would be happy if someone could point out some algorithms or categories of algorithms for this purpose. It would feel much better to rely on an existing and proved algorithm than some home-made stuff.

Note: In reality, the number of items is very large so testing all different permutations is NOT an option.

Answer 1

Nice greedy solution: for the first place take maximum number. For each next place take maximum from untaken numbers before that satisfy your condition. If you place all numbers - you have found a solution. Otherwise the solution doesn't exist, why - it's an exercise for you.

My proof: imagine a solution exists. Show, that my algorithm will find it. Let's a_1, ..., a_n - any solution. Let a_i - maximum element. Then a_i, a_{i-1}, ..., a_1, a_{i+1}, a_{i+2}, ..., a_n is a solution too, because a_1 <= a_i, a_1 + a_{i+1} <= a_i + a_{i+1}, so (a_i, a_{i+1}) is a good pair. Next, let a_1, ..., a_j is element according to my solution. Show, that a_{j+1} can be element, as my solution suppose to. Let a_i - maximum from a_{j+1}, .., a_n. Then a_1, ..., a_j, a_i, a_{i-1}, ..., a{j+1}, a_{i+1}, ..., a_n is a solution too. It shows that algo always find solution.

Answer 2

Big items can only be next to small items.

1. Sort the list
2. Cut in half
3. Reverse second half
4. Swap halves
5. Shuffle (take first item from each half, repeat)

Example: [1,3,8,4,2,4,1,7]

1. [1,1,2,3,4,4,7,8]
2. [1,1,2,3] [4,4,7,8]
3. [1,1,2,3] [8,7,4,4]
4. [8,7,4,4] [1,1,2,3]
5. [8,1,7,1,4,2,4,3]

I'm pretty sure you can't do better than this. If the business rule is violated anyway there is no solution. Prove/Counterexample left as an exercise ;-)

Edit: Take biggest item first!

Answer 3

This looks similar to a bin packing problem, take a look at (eg) http://en.wikipedia.org/wiki/First_fit_algorithm

I'm pretty sure it's not the same, but it may give you some clues.

You also need to consider what would happen if a sigle item is over the limit - how would you deal with that?