The voracious algorithms can be solved with or without ordering, it depends on the strategy that is decided to use, I have solved it doing previous ordering of the set of candidates . Let's go with the code:
Class that represents the voting entity, has the probability of voting, a cost, an applied cost, that is, how much money we are supposed to get a 100% probability to obtain the vote and a voter's identifier.
public class Votante {
private final String idVotante;
private final float probabilidadVoto;
private final int costo;
private final float costoAplicado;
public Votante(String idVotante, float probabilidadCandidato, int costo) {
this.idVotante = idVotante;
this.probabilidadVoto=probabilidadCandidato;
this.costo = costo;
this.costoAplicado = (1 - probabilidadVoto) * costo;
}
public String getIdCandidato() {
return idVotante;
}
public float getProbabilidadVoto() {
return probabilidadVoto;
}
public int getCosto() {
return costo;
}
public float getCostoAplicado() {
return this.costoAplicado;
}
@Override
public String toString() {
StringBuffer str=new StringBuffer("Votante: ").append(idVotante)
.append(" - Probabilidad de voto: ").append(probabilidadVoto)
.append(" - Costo de corrupcion: ").append(costo)
.append(" - Costo en base a probabilidad: ").append(costoAplicado);
return str.toString();
}
}
On the other hand we are going to implement a Comparator to order our candidate set so that the probability of voting is greater or lesser, if the same probability is given then order for the cost from least to greatest:
public class ComparadorDeVotantes implements Comparator<Votante> {
@Override
public int compare(Votante v1, Votante v2) {
if(v1.getProbabilidadVoto()==v2.getProbabilidadVoto()) {
return v1.getCosto() < v2.getCosto() ? -1 : v1.getCosto() == v2.getCosto() ? 0: -1 ;
}
return v1.getProbabilidadVoto() > v2.getProbabilidadVoto() ? -1 : 1;
}
}
I define a trivial interface to represent the functionality of the algorithm, receive a set cadidates and return a set solution :
public interface AlgoritmoVoraz<T> {
public List<T> procesa(List<T> candidatos);
}
Now we implement a class to solve this problem
public class AlgoritmoCostoCorrupcion implements AlgoritmoVoraz<Votante> {
private String candidatoElectoral;
public AlgoritmoCostoCorrupcion(String candidatoElectoral) {
this.candidatoElectoral=candidatoElectoral;
}
@Override
public List<Votante> procesa(List<Votante> listaDeVotantes) {
//ordenamos el conjunto candidatos
Collections.sort(listaDeVotantes, new ComparadorDeVotantes());
//creamos el conjunto solucion, inicialmente vacio
List<Votante> solucion = new ArrayList<Votante>();
//guardamos el numero de elementos del conjunto candidato para poder
//calcular porcentaje de procesamiento posteriormente
int elementosTotales = listaDeVotantes.size();
//sumatorio para calcular el costo de corrupcion de los votantes
float costoCorrupcion = 0;
//iteramos mientras no tengamos una solucion valida
while (!esSolucion(solucion.size(), elementosTotales, 70)) {
//como el conjunto candidato esta ordenado la seleccion es
//tan simple como obtener siempre el primero
Votante candidato = seleccionarCandidato(listaDeVotantes);
//sumamos
costoCorrupcion = costoCorrupcion + candidato.getCostoAplicado();
//añadimos al conjunto solucion
solucion.add(candidato);
//eliminamos del conjunto candidato
listaDeVotantes.remove(candidato);
}
//conjunto solucion
return solucion;
}
//obtiene el primer elemento del conjunto candidato
private Votante seleccionarCandidato(List<Votante> listaDeVotantes) {
return listaDeVotantes.get(0);
}
//es solucion cuando se han procesado el 70% o mas de los elementos
//del conjunto candidato, no es necesario mas al estar ordenados
private boolean esSolucion(int elementosProcesados, int elementosMaximos, int porcentajeMinimo) {
return (elementosProcesados * 100) / elementosMaximos > porcentajeMinimo;
}
//muestra resultado
public void print(List<Votante> solucion) {
float costoCorrupcion=0;
System.out.println("Datos del conjunto solucion:");
for (Votante elementoDeSolucion : solucion) {
System.out.println("\t"+elementoDeSolucion.toString());
costoCorrupcion = costoCorrupcion + elementoDeSolucion.getCostoAplicado();
}
System.out.println("El coste de corrupcion minimo es de : " + costoCorrupcion + " para el candidato: "
+ candidatoElectoral + "con al menos el 70% de los votantes");
}
}
Test to check:
public class AlgoritmoCostoCorrupcionTest {
@Test
public void testProcesa() {
List<Votante> listaDeVotantes=new ArrayList<Votante>();
listaDeVotantes.add(new Votante("Votante1",0.2f,4));
listaDeVotantes.add(new Votante("Votante2",0.1f,3));
listaDeVotantes.add(new Votante("Votante3",0.8f,2));
listaDeVotantes.add(new Votante("Votante4",0.5f,5));
listaDeVotantes.add(new Votante("Votante5",0.6f,3));
listaDeVotantes.add(new Votante("Votante6",0.2f,3));
listaDeVotantes.add(new Votante("Votante7",0f,5));
AlgoritmoCostoCorrupcion ccc=new AlgoritmoCostoCorrupcion("Candidato A");
List<Votante>solucion=ccc.procesa(listaDeVotantes);
ccc.print(solucion);
assertThat(solucion.size(),is(equalTo(5)));
}
}
I hope it will be helpful, without prior planning the implementation is more complicated for me, the same thing you do not think so.