Formazione MLB ottimale utilizzando la variante Zaino

Question

Sto scrivendo un programma per trovare la migliore lineup MLB utilizzando una soluzione zaino. Per questo passo nei dati del giocatore che ha un valore calcolato e un salario. Il salario sarà il mio "peso" in termini di problemi con lo zaino.

Il mio problema non è in grado di selezionare i giocatori, ma selezionare la formazione più ottimale. Sto scegliendo un lanciatore, un centro, il primo baseman, il secondo baseman, il terzo baseman, il short stop e tre outfielders. Posso farlo tutto con successo. Voglio che il mio "peso" sia 36.000, ma al momento sto solo scegliendo una formazione con un totale di 21.000.

Ecco il mio codice zaino:

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

Sto facendo un errore palese che io sono solo, non vedendo, o è la mia logica completamente fuori?

Answer 1

Stai verificando la soluzioneIl giusto? La logica per accettare le posizioni non è inclusa nella logica dello zaino, il che significa che solutionSet è un filtro sulla parte superiore della soluzione dello zaino. Sei arrivato alla giusta soluzione di zaino, ma perché, in cima alla soluzione, stai controllando se la posizione era già piena, alcuni elementi sono stati eliminati da solutionSet (articoli che stavano combattendo per la stessa posizione) e il peso totale diminuito.