(UVA) Ecological Bin Packing - Solution 1

I used Brute Force to solve this problem. Here, I used some nestled for loops to find all the possible solutions.


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

class Main  {
    public static int[] binsContent;
    public static String colorsLetters = "BGC";
   
    public static int calc(int b, int g, int c) {
        int sum = 0;
        for (int i = 0; i < 3; i++) {
            if (i != b) {
                sum += binsContent[i];
            }
        }
        for (int i = 3; i < 6; i++) {
            if (i%3 != g) {
                sum += binsContent[i];
            }
        }
        for (int i = 6; i < 9; i++) {
            if (i%3 != c) {
                sum += binsContent[i];
            }
        }
       
        return sum;
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        while (line != null) {
            String[] s = line.split("\\s");
           
            binsContent = new int[9];
            for (int i = 0; i < 9; i++) {
                binsContent[i] = Integer.parseInt(s[i]);             
            }

            int index = 0;
            Solution[] solutions = new Solution[6];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    for (int k = 0; k < 3; k++) {
                        if (i != j && j != k && i != k) {
                            solutions[index] = new Solution((colorsLetters.charAt(i)+""+colorsLetters.charAt(j)+""+colorsLetters.charAt(k)), calc(i, j, k));
                            index++;
                        }
                    }
                }
            }
           
            Arrays.sort(solutions);
           
            System.out.println(solutions[0].colors + " " + solutions[0].movements);
          
            line = br.readLine();
        }
                   
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Solution implements Comparable<Solution> {
    String colors;
    int movements;
   
    public Solution(String colors, int movements) {
        this.colors = colors;
        this.movements = movements;
    }
   
    public int compareTo(Solution s) {
        if (this.movements == s.movements) {
            return colorsComparator.compare(this, s);
        }
       
        return this.movements-s.movements;
    }
   
    public static Comparator<Solution> colorsComparator = new Comparator<Solution>() {
        public int compare(Solution s1, Solution s2) {
            return s1.colors.compareTo(s2.colors);
        }
    };
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução