Voracious Algorithms


I am a student of programming and I would like to know if any of them can give me an idea of how to perform the following problem using voracious algorithms.


Find a good solution to the following problem using a voracious algorithm. Explain the operation of the algorithm: which is the set of candidates, the selection function, the function to add an element to the solution, the criterion of completion, the cost criterion, etc.


In a vote there are n candidates and m voters. The probability that a voter i votes the candidate j is known a priori, and is given by P [i, j] . Any voter to can be coerced into voting for the candidate we want, for example p , for which we have to pay C [a] ptas With this, we make sure that P [a, p] = 1 , and P [a, j] = 0 , for j ≠ p .


The objective is to spend the minimum amount of money, coercing the necessary voters, to ensure that a given p candidate will take at least 70% of the votes (according to the odds expected). The solution will consist of the list of voters to be coerced.


Apply the algorithm designed to the following example: n = 2 candidates, m = 7 voters, p = 1. Percentages and costs of coercion:

        |  1  |  2  |  3  |  4  |  5  |  6  | 7 |
P[i, 1] | 0.2 | 0.1 | 0.8 | 0.5 | 0.6 | 0.2 | 0 |
P[i, 2] | 0.8 | 0.9 | 0.2 | 0.5 | 0.4 | 0.8 | 1 |
C[i]       4     3     2     5     3     3    5
asked by Charlie 25.04.2016 в 03:25

2 answers


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.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;

  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> {

  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) {

  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);
        costoCorrupcion = costoCorrupcion + candidato.getCostoAplicado();
        //añadimos al conjunto solucion
        //eliminamos del conjunto 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) {
        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 {

  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");



I hope it will be helpful, without prior planning the implementation is more complicated for me, the same thing you do not think so.

answered by 27.04.2016 в 02:01

The voracious algorithms decide the most beneficial option in each state of the problem. In this case I think the idea is to choose the voter first with the lowest cost that benefits the candidate's vote more 1. Then the next one in cost / benefit and so on until reaching the goal of ensuring 70%. I hope it helps you.

answered by 25.04.2016 в 18:04