The UVa 102: Ecological Bin Packing can be solved using brute-force search, as outlined in the following Java code snippet. Note that, the primary function getOPTConfiguration iterates over all possible bin arrangements, and determines the arrangement that requires minimum bottle moves for a given problem instance.

	import java.io.PrintWriter;
	import java.util.Scanner;

	class Main {

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

	private char[] types;
	private int[][] permutations;

	private static final int _NO_OF_BINS = 3;
	private static final int _BOTTLE_TYPES = 3;

	private int optMoveCount;
	private String optPermutation;


	public Main(){
	types = new char[]{'B','G','C'};
	permutations = new int[][] {
	{0,1,2},
	{0,2,1},
	{1,0,2},
	{1,2,0},
	{2,0,1},
	{2,1,0}
	};
	}

	private String permutationString(int permutationIndex){
	String retString = "";
	for(int i = 0;i<_NO_OF_BINS;i++){
	retString += types[permutations[permutationIndex][i]];
	}
	return retString;
	}

	private void initState(){
	optMoveCount = -1;
	optPermutation = "";

	}

	/**
	* A brute-force algorithm to determine a bin
	* configuration that yield
	* optimal (minimum) bin movements.
	* @param input
	* @return a String that represents OPT bin
	* configuration that yields minimum movement.
	*/
	String getOPTConfiguration(int[][] input){
	initState();

	for (int pi = 0;pi<permutations.length;pi++){
	int currentMoveCount = 0;

	for (int bno=0;bno<_NO_OF_BINS;bno++){
	int allowedType = permutations[pi][bno];
	for(int btype = 0; btype<_BOTTLE_TYPES;btype++){
	if (allowedType!=btype){
	currentMoveCount += input[bno][btype];
	}
	}
	}

	String currentPermutation = permutationString(pi);

	if ((this.optMoveCount == -1) \|\|
	(currentMoveCount < optMoveCount) \|\|
	((currentMoveCount == optMoveCount) && (currentPermutation.compareTo(optPermutation)<0))){

	this.optMoveCount = currentMoveCount;
	this.optPermutation = currentPermutation;
	}
	}

	return optPermutation+" "+optMoveCount;
	}

	public void solve(){
	int[][] inputBottles = new int[_NO_OF_BINS][_BOTTLE_TYPES];
	while (in.hasNextInt()){
	for(int i = 0;i<_NO_OF_BINS;i++){
	for (int j=0;j<_BOTTLE_TYPES;j++){
	inputBottles[i][j] = in.nextInt();
	}
	}
	out.println(getOPTConfiguration(inputBottles));
	}
	}


	public static void main(String[] args) {
	Main binPackingSolver = new Main();
	binPackingSolver.solve();
	}

	}

view raw uva102.java hosted with ❤ by GitHub

Please leave a comment if you have any question/comment. Happy coding!

The UVa 100: The 3n+1 Problem is about collatz problem, which we have discussed in details in a recent post. The following Java code describes a brute-force algorithm to solve this problem. In addition, a memoization technique is incorporated to reduce redundant computations and thereby, to enhance efficiency of this brute-force algorithm.

	import java.util.*;
	import java.io.*;

	class Main {
	public static void main(String[] args) throws Exception{
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out, true);

	while(in.hasNextInt()){
	int i = in.nextInt();
	int j = in.nextInt();

	int from = Math.min(i, j);
	int to = Math.max(i, j);

	int max = 0;

	for (int ii = from;ii<=to;ii++){
	max = Math.max(max, computeCycleLength(ii));
	}

	out.printf("%d %d %d\n", i, j, max);
	}

	}

	private static int computeCycleLength(long n) {

	if (n==1)
	return 1;
	if (n<_MaxValue && memo[(int)n] != 0)
	return memo[(int)n];

	// computing length of collatz cycle
	int len = 1 + computeCycleLength(nextCollatz(n));

	// storing it in cache
	if (n<_MaxValue)
	memo[(int)n] = len;
	return len;
	}


	private static int _MaxValue = 1000000;
	public static int[] memo = new int[_MaxValue];

	public static long nextCollatz(long n){

	if (n%2==0)
	return n/2;
	else
	return n*3+1;
	}
	}

view raw uva100.java hosted with ❤ by GitHub

Please leave a comment if you have any query. Thank you.

Category: Brute-force

UVa 102. Ecological Bin Packing | with Brute-force search

UVa 100. The 3n+1 Problem: Solving with a Brute-force Algorithm

See Also