From dbac348f9052f998514714e7fa07c502b6e8fb38 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Fri, 20 Jun 2014 11:19:12 +0200 Subject: [PATCH] Cleaned up the code and improved report --- LubbersReport.tex | 24 ++++++++++-------------- LubbersSolver.java | 43 ++++++++++++++++++------------------------- 2 files changed, 28 insertions(+), 39 deletions(-) diff --git a/LubbersReport.tex b/LubbersReport.tex index e175b99..ceaa068 100644 --- a/LubbersReport.tex +++ b/LubbersReport.tex @@ -45,8 +45,8 @@ \end{center} The assignment is to implement a \textit{\href{http://www.java.com}{Java}} -program that optimizes the assignment of pets to children so that the sum of -all the compatibility values between pets and children is the maximum possible. +program that maximizes the sum of the compatibiliy values of the pet-child +combination. \section{Implementation} \subsection{Brute Force} @@ -55,15 +55,13 @@ every possible combination of pets and children and then takes the one with the highest value. This corresponds with the pseudocode specified together with a rough estimate of the complexity in Listing~\ref{lst:brute_force}. The algorithm, due to calculating all the values the algorithm has a complexity -within $\mathcal{O}(n!)$. -This is because there are $n!$ permutations possible for $n$ children. -\begin{lstlisting}[ - caption={Brute Force approach}, - label={lst:brute_force}, - keywords={[3]loop,put,return} -] +within $\mathcal{O}(n!)$. This is because there are $n!$ permutations possible for $n$ children. +Because of the rapid growth due to the complexity level the algorithm doesn't +scale up well. +\begin{lstlisting}[caption={Brute Force approach}, label={lst:brute_force}, + keywords={[3]loop,put,return}] n! - loop over all permutations -c1 - put compatibility in list +n - put compatibility in list c1 - return maximum compatibility rating from list \end{lstlisting} @@ -76,10 +74,8 @@ estimate of the complexity in Listing~\ref{lst:improved}. The algorithm has a complexity lies in the $\mathcal{O}(nm)$ because the main loop repeats at maximum $n$ or $m$ times and the searching within the loop has a complexity of $n$ if the loop runs $m$ times and $m$ otherwise. -\begin{lstlisting}[ - caption={Improved approach}, - label={lst:improved}, - keywords={[3]while,create,put,return,find,remove} +\begin{lstlisting}[caption={Improved approach}, label={lst:improved}, + keywords={[3]while,create,put,return,find,remove} ] n - create list result of length n and initialize with -1 n+m - create list rows/columns that contain pairs of indices and sums of values diff --git a/LubbersSolver.java b/LubbersSolver.java index 8a280b0..7ae5a0d 100755 --- a/LubbersSolver.java +++ b/LubbersSolver.java @@ -29,10 +29,10 @@ public class LubbersSolver implements IPetproblemSolver { } rows.add(new SimpleEntry(i, sum)); } - for (int i = 0; i < m; i++) { + for (int i = 0; i < m; i++) cols.add(new SimpleEntry(i, col_sums[i])); - } - //Sort the lists so the rows and columns with the least amount of positive compatibilities + + //Sort the lists so the rows and columns with the least amount of positive compatibilities are up front Comparator> comp = new Comparator>() { @Override public int compare(SimpleEntry a, SimpleEntry b) { @@ -47,7 +47,6 @@ public class LubbersSolver implements IPetproblemSolver { * 2. Find the match with the lowest sum and still positive compatibility for that row or column * 3. Select smallest from those indices */ - SimpleEntry MINIMUM = new SimpleEntry(-1, Integer.MAX_VALUE); while (!(rows.isEmpty() || cols.isEmpty())) { //1. Find the row or column with the lowest sum(least available matches) SimpleEntry row_l = rows.peekFirst(); @@ -58,35 +57,29 @@ public class LubbersSolver implements IPetproblemSolver { //Remove the current lowest row sum rows.remove(row_l); //3. Find smallest column that has compatibility 1 - SimpleEntry smallest = MINIMUM; - for (SimpleEntry e : cols) { - if (e.getValue() < smallest.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1) { - smallest = e; - } - } + SimpleEntry min = new SimpleEntry(-1, Integer.MAX_VALUE); + for (SimpleEntry e : cols) + if (e.getValue() < min.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1) + min = e; //No pets left that have a positive compatibility - if (smallest.getKey() == -1) { - continue; + if (min.getKey() != -1) { + cols.remove(min); + result[row_l.getKey()] = min.getKey(); } - cols.remove(smallest); - result[row_l.getKey()] = smallest.getKey(); //2. The column is the lowest } else { //Remove the current lowest column sum cols.remove(col_l); //3. Find smallest row that has compatibility 1 - SimpleEntry smallest = MINIMUM; - for (SimpleEntry e : rows) { - if (e.getValue() < smallest.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1) { - smallest = e; - } - } - //No pets left that have a positive compatibility - if (smallest.getKey() == -1) { - continue; + SimpleEntry min = new SimpleEntry(-1, Integer.MAX_VALUE); + for (SimpleEntry e : rows) + if (e.getValue() < min.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1) + min = e; + //If there is a pet left, remove it and assign it + if (min.getKey() != -1) { + rows.remove(min); + result[min.getKey()] = col_l.getKey(); } - rows.remove(smallest); - result[smallest.getKey()] = col_l.getKey(); } } return result; -- 2.20.1