102 – Ecological Bin Packing

Problem: You are given three recycling bins, each containing a specified number of brown, green and clear bottles. In order to be recycled, the bottles will need to be moved so that each bin contains bottles of only one color. The problem is to minimize the number of bottles that are moved. You may assume that the only problem is to minimize the number of movements between boxes.

For the purposes of this problem, each bin has infinite capacity and the only constraint is moving the bottles so that each bin contains bottles of a single color. The total number of bottles will never exceed 2^31. [source]

The input will be a string of 9 numbers like this – 5 10 5 20 10 5 10 20 10, where the numbers represent the number of brown, green and clear glasses in each of the bins. (Ex: Bin 1 has 5 brown, 10 green and 5 clear glasses.)

You should output the minimum number of moves required and the arrangement that ensures the minimal number of moves.

Category: counting, combinatorics, discrete math

Discussion: One of the simplest problems over there. No tricks involved; just compute the number of moves required for each permutation of the colours (brown, green, clear; brown, clear, green; etc.) and chose the one that has the minimal moves. Well, in this case, since there are only 3 bottles, you can simply list the 6 permutations. In the general case, you’ll have to enumerate all permutations. The general case of this problem, where there are n bins, is a difficult optimization problem. I am not sure if there are any solutions to it that don’t require the enumeration of all permutations.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: