Skip to content

Instantly share code, notes, and snippets.

@adilakhter
Last active December 14, 2015 16:08
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save adilakhter/5112924 to your computer and use it in GitHub Desktop.
uvA 102: Ecological Bin Packing
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();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment