UVA – 102 – Ecological Bin Packing

  • ID : UVA – 102 – Ecological Bin Packing
  • Submissions :
    • Java – Accepted
  • Difficulty : Easy
  • Type : Adhoc, Enumeration, Permutations
  • Time for Submission : 30 minutes
  • Solution Description :
    • the sample space contains only 6 permutations so pre-enumerating them and finding there minimum is the best case.
  • Problems :
    • Didn’t think of a dynamic solution for a larger n

</span>
<pre>import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int B = 0, G = 1, C = 2, min, minIndex = 0, total = 0;
		int[][] permutations = { { B, C, G }, { B, G, C }, { C, B, G },
				{ C, G, B }, { G, B, C }, { G, C, B } };
		String[] sol = { "BCG ", "BGC ", "CBG ", "CGB ", "GBC ", "GCB " };
		int[][] bins = new int[3][3];
		ArrayList<String> cases = new ArrayList<String>();
		while (in.hasNext()) {
			total=0;
			for (int i = 0; i < 3; total += bins[i][B] + bins[i][G] + bins[i][C],i++)
				bins[i] = new int[] { in.nextInt(), in.nextInt(), in.nextInt() };
			min = total;
			for (int perm = 0; perm < permutations.length; perm++) {
				int currentCase = total;
				for (int color = 0; color < 3; color++)
					currentCase -= bins[color][permutations[perm][color]];

				if (currentCase < min) {
					min = currentCase;
					minIndex = perm;
				}
			}
			cases.add(sol[minIndex]+min);
		}
		for(String s : cases)
			System.out.println(s);
	}
}
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: