Programa para equipos

[marlanga]

Backtracking puro, sobre un algoritmo óptimo de selección general (cualquier número de equipos, cualquier diferencia máxima de tamaño de equipo).

Se puede mejorar mucho, haciendo ramificación y poda. Pero como las operaciones que realiza son sencillas, para 20 elementos no tiene demasiado coste de tiempo (2 segundos, por lo menos en una cpu i5).
A partir de ahí empieza a dispararse el tiempo, por lo que para meter mas elementos se estaría obligado a podar.

http://jsfiddle.net/marlanga/1aqzp30q/

Código Javascript:

Array.prototype.sum = function() {
    return this.length ? this.reduce(
        function(a, b) {
            return a + b;
        }
    ) : 0;
}
 
function Equipo(){
    this.miembros = [];
}
 
Equipo.prototype.pop = function() {
    return this.miembros.pop();
}
 
Equipo.prototype.push = function(miembro) {
    this.miembros.push(miembro);
}
 
Equipo.prototype.sumar = function() {
    return this.miembros.sum();
}
 
Equipo.prototype.length = function() {
    return this.miembros.length;
}
 
Equipo.prototype.clonar = function() {
    var clon = new Equipo();
    for (var i = 0, n = this.miembros.length; i < n; i++) {
        clon.push(this.miembros[i]);
    }
    return clon;
}
 
function RyP(disponibles, numero_equipos, cantidad_miembros_diferencia) {
    this.disponibles = disponibles;
    this.equipos=[];
    this.nEquipos = numero_equipos;
    this.cantidad_miembros_diferencia = cantidad_miembros_diferencia;
 
    this.mejor_solucion = {
        diferencia : Infinity,
        equipos : null
    };
 
    this.crearEquipos();
}
 
RyP.prototype.crearEquipos = function() {
    for(var i = 0; i < this.nEquipos; i++) {
        this.equipos.push(new Equipo());
    }
}
 
RyP.prototype.exec = function() {
    if (this.disponibles.length === 0) {
        this.comparaSolucion();
    } else {
        var miembro = this.disponibles.pop();
        for(var i = 0; i < this.nEquipos; i++) {
            this.equipos[i].push(miembro);
            this.exec();
            this.equipos[i].pop();
        }
        this.disponibles.push(miembro);
    }
}
 
RyP.prototype.comparaSolucion = function() {
    if (this.maximaDiferenciaCantidadMiembros() > this.cantidad_miembros_diferencia) return;
    var diff = this.maximaDiferenciaPesoEquipo();
    if (diff >= this.mejor_solucion.diferencia) return;
 
    this.mejor_solucion.diferencia = diff;
    var clon_equipos = [];
    for(var i = 0; i < this.nEquipos; i++) {
        clon_equipos.push(this.equipos[i].clonar());
    }
    this.mejor_solucion.equipos = clon_equipos;
}
 
RyP.prototype.maximaDiferenciaCantidadMiembros = function() {
    return this.maximaDiferencia();
}
 
RyP.prototype.maximaDiferenciaPesoEquipo = function() {
    return this.maximaDiferencia(true);
}
 
RyP.prototype.maximaDiferencia = function(condicion) {
    var menor = condicion ? this.equipos[0].sumar() : this.equipos[0].length();
    var mayor = menor;
 
    for(var i = 1; i < this.nEquipos; i++) {
        var length = condicion ? this.equipos[i].sumar() :  this.equipos[i].length();
        menor = Math.min(length, menor);
        mayor = Math.max(length, mayor);
    }
 
    return Math.abs(mayor - menor);
}
 
 
 
var miembros = [51,49,35,32,31];
var numero_equipos = 2;
var diferencia_maxima_cantidad_miembros_por_equipo = 1;
var resolvedor = new RyP(miembros,numero_equipos, diferencia_maxima_cantidad_miembros_por_equipo);
resolvedor.exec();
console.log(resolvedor.mejor_solucion);