UVa 102: Ecological Bin Packing

UVa 102: Ecological Bin Packing

Written by on 2 January 2013

Topics: UVa Online Judge

We’re back to doing another simple UVa Online Judge problem, and this time we take on problem 102, Ecological Bin Packing. In the problem we are asked to solve a bin packing problem about recycling glass. It can be easily solved with brute force, but requires careful coding. Enough yapping, let’s take a look at the problem description.

Interpretation

We have three bins, each of which contains some number of bottles. There are three types of bottles; brown, green and clear, denoted by “B”, “G” and “C”, respectively. We are given how many  bottles of each type are in each bin.

In this particular example are 9 bottles. The first bin contains two brown bottles and one clear bottle, the second bin contains four green bottles, and the third bin contains two clear bottles. The problem description tells us that we are recycling the bottles, and we must sort them so that there is only one type of bottles in each bin. For the example above, we could have moved the two brown bottles in the first bin to the third bin, and the two clear bottles in the third bin to the first bin.

Now there is only one type of bottles in each bin; clear bottles in the first bin, green bottles in the second bin, and brown bottles in the third bin. We had to move four bottles to accomplish this. But lets go back to the previous example. We can also achieve this kind of sorting by moving only one bottle: the clear bottle in the first bin to the third bin.

In fact, that is exactly what the problem description is asking about: the minimum number of bottles that need be moved in order to have only one type of bottle in each bin. We are also asked to return in what order the bottle types will be after they have been moved to their correct places. For example, in the last image, brown bottles are in the first bin, green bottles in the second bin and clear bottles in the third bin. So the order is brown, green, clear, or simply “BGC”. If there are multiple orders that would result in the minimum move count, then we are asked to output the order which has the  alphabetically first  string representation. Therefore “CBG” would be chosen instead of “GBC”, assuming they both have the minimum move count.

Implementation

So how do we find the minimum move count? First we must notice that if we decide some order in which to put the bottle types, for example “CBG”, then we can easily compute how many moves we would need by counting how many bottles are in the wrong bin according to the bottle type order. There are only possible permutations of the bottle order that we can choose, so looping through each permutation and computing the move count of that particular order is completely feasible. Then we just keep track of the lowest move count, along with its alphabetically first bottle type order, that we’ve found so far.

Since there are only six possible permutations, we’re probably faster to manually write each of them down instead of writing a special function to generate them. Then we also need to be careful when we write the implementation – there are a lot of multiple dimensional arrays and indices that can go wrong. When we’re finished, the code might look something like this:

Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out, true);

// types of bottles: brown, green, clear
char[] bottleType = { 'B', 'G', 'C' };

// all 6 possible permutations of bottle type-to-bin mappings
int[][] permutations = {
	{ 0, 1, 2 },
	{ 0, 2, 1 },
	{ 1, 0, 2 },
	{ 1, 2, 0 },
	{ 2, 0, 1 },
	{ 2, 1, 0 }
};

// bottles[i][j] are the number of type j bottles in bin i
int[][] bottles = new int[3][3];

// while there is a test case left
while (in.hasNextInt()) {

	// the minimum bottle move-count so far,
	// initially -1 to indicate that we haven't found anything yet
	int minCount = -1;

	// the string representation of the permutation with the minimum bottle move-count so far
	String minPerm = "";

	// read in the bottle counts
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			bottles[i][j] = in.nextInt();
		}
	}

	// loop through each permutation
	for (int i = 0; i < permutations.length; i++) {

		// count how many bottles need to be moved
		int curCount = 0;

		// j is the current bin, and permutations[i][j] is the bottle-type that we want in that bin
		for (int j = 0; j < 3; j++) {

			// go through all each bottle-type k
			for (int k = 0; k < 3; k++) {

				// if the current bottle type is not supposed to be in the current bin
				if (permutations[i][j] != k) {

					// then we need to move them, and we're counting how many we need to move
					curCount += bottles[j][k];
				}
			}
		}

		// the string representing the current permutation, example: "GCB"
		String curPerm = "" + bottleType[permutations[i][0]] + bottleType[permutations[i][1]] + bottleType[permutations[i][2]];

		// if this is the first permutation we try, or if the current bottle move-count is less than the minimum bottle move-count,
		// or the current bottle move-count is equal to the minimum bottle move-count and the permutation string is less than the
		// permutation string of the minimum bottle move-count
		if (minCount == -1 || curCount < minCount || (curCount == minCount && curPerm.compareTo(minPerm) < 0))
		{
			// then this is the best permutation so far
			minCount = curCount;
			minPerm = curPerm;
		}
	}

	// print the minimum bottle move-count and the permutation string
	out.println(minPerm + " " + minCount);
}

Conclusion

And that pretty much sums it up. The complete source code is located here.
Leave a comment if you have any questions, or if you want to tell us how you solved the problem.

1 Comment For This Post I'd Love to Hear Yours!

  1. Siegrift says:

    nice.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.