ナップザック変異体を使用した最適なMLBラインアップ

Question

ナップザックソリューションを使用して最良のMLBラインナップを見つけるプログラムを作成しています。これについては、プレーヤーの計算値と給与を持つプレーヤーデータを渡します。ナップザック問題の点で、給料は私の「体重」になります。

私の問題は選手を選ぶことができず、むしろ最適なラインナップを選択することです。私は投手、センター、一塁手、二塁手、三塁手、ショートストップ、そして3人の外野手を選んでいます。私はこれをすべて成功裏に行うことができます。私は自分の「体重」を36,000にしたいが、現在は合計21,000のラインナップしか選択していない。ここで

は私のナップザックコードです：

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

私はただ見ていないのです露骨な間違いを犯して、または完全にオフに私のロジックであるだろうか？

Answer 1

あなたはsolutionSetを正しく確認していますか？位置を受け取るロジックは、ナップザックロジックには含まれていません。つまり、solutionSetはナップザックソリューションの上にあるフィルタです。あなたは右のナップザックソリューションに到達しましたが、ソリューションの上に、そのポジションがすでに満たされているかどうか、ソリューションセットからいくつかのアイテムが削除されているかどうか（同じポジションで戦っていたアイテム）減少した。