javascript - Optimal MLB alineación con la variante Knapsack

multidimensional-array knapsack-problem

Question

Estoy escribiendo un programa para encontrar la mejor alineación MLB posible con una solución de mochila. Para esto paso los datos del jugador que tienen el valor y el salario calculados por los jugadores. El salario será mi "peso" en términos de ser un problema de mochila.

Mi problema no es poder seleccionar jugadores, sino seleccionar la alineación más óptima. Estoy eligiendo un lanzador, un centro, primera base, segunda base, tercera base, parada corta y tres jardineros. Puedo hacer todo esto con éxito. Quiero que mi "peso" sea de 36,000, pero actualmente solo elijo una alineación con un total de 21,000.

Aquí está mi código de mochila:

CalculateLineUp.prototype.findOptimalLineUp = function(data, capacity) {
  var items = data.data;
  var idxItem   = 0,
      idxCapSpace = 0,
      idxPosition = 0,
      oldMax    = 0,
      newMax    = 0,
      numItems  = items.length,
      weightMatrix  = new Array(numItems+1),
      keepMatrix    = new Array(numItems+1),
      positionArray = new Array("P", "C", "1B", "2B", "3B", "SS", "OF", "OF", "OF"),
      solutionSet   = [];

  // Setup matrices
  for(idxItem = 0; idxItem < numItems + 1; idxItem++){
    weightMatrix[idxItem] = new Array(capacity+1);
    keepMatrix[idxItem]   = new Array(capacity+1);
  }

  // Build weightMatrix from [0][0] -> [numItems-1][capacity-1]
  for (idxItem = 0; idxItem <= numItems; idxItem++){
    for (idxCapSpace = 0; idxCapSpace <= capacity; idxCapSpace++){  

          // Fill top row and left column with zeros
          if (idxItem === 0 || idxCapSpace === 0){
            weightMatrix[idxItem][idxCapSpace] = 0;
          }

          // If item will fit, decide if there''s greater value in keeping it,
          // or leaving it
          else if (items[idxItem-1]["Salary"] <= idxCapSpace){
            newMax = items[idxItem-1]["Value"] + weightMatrix[idxItem-1][idxCapSpace-items[idxItem-1]["Salary"]];
            oldMax = weightMatrix[idxItem-1][idxCapSpace];

            // Update the matrices
            if(newMax > oldMax ){ 
              weightMatrix[idxItem][idxCapSpace]  = newMax;
              keepMatrix[idxItem][idxCapSpace]    = 1;

            }
            else{
              weightMatrix[idxItem][idxCapSpace]  = oldMax; 
              keepMatrix[idxItem][idxCapSpace]    = 0;
            }
          }

          //Else, item can''t fit; value and weight are the same as before
           //else
             //weightMatrix[idxItem][idxCapSpace] = weightMatrix[idxItem-1][idxCapSpace];
    }
  }

  // Traverse through keepMatrix ([numItems][capacity] -> [1][?])
  // to create solutionSet
  idxCapSpace = capacity;
  idxItem   = numItems;
  for(idxItem; idxItem < capacity; idxItem--){
    if(keepMatrix[idxItem][idxCapSpace] === 1 && !this.filledAllPositions(items[idxItem - 1]["Position"])){
      solutionSet.push(items[idxItem - 1]);
      idxCapSpace = idxCapSpace - items[idxItem - 1]["Salary"];
    }
  }
  return {"maxValue": weightMatrix[numItems][capacity], "set": solutionSet};
};

¿Estoy cometiendo un error flagrante que simplemente no estoy viendo, o mi lógica está completamente desconectada?

Answer 1

Usted está revisando la solución ¿Está bien? La lógica para aceptar posiciones no está incluida en la lógica de la mochila, lo que significa que el conjunto de soluciones es un filtro en la parte superior de la solución de mochila. Usted llegó a la solución de mochila correcta, pero debido a que, además de la solución, está verificando si la posición ya estaba ocupada, se eliminaron algunos elementos del conjunto de soluciones (elementos que estaban luchando por la misma posición) y el peso total disminuido