Bactraking para reparto de pesos en equipos

by marlanga

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