Оптимальная линейка MLB с использованием варианта рюкзака

Question

Я пишу программу, чтобы найти наилучшую возможную линейку MLB, используя рюкзак. Для этого я передаю данные об игроках, в которых рассчитана стоимость игрока и зарплата. Заработная плата будет моим "весом" с точки зрения того, чтобы быть проблемой ранца.

Моя проблема не в том, чтобы выбрать игроков, а выбрать наиболее оптимальный состав. Я выбираю кувшин, центр, первый человек с низов, второй человек с низов, третий человек с низов, короткие остановки и три аутфилдеры. Я могу сделать все это успешно. Я хочу, чтобы мой "вес" составлял 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 - это фильтр поверх решения ранца. Вы действительно нашли правильное решение для рюкзака, но поскольку поверх решения вы проверяете, была ли позиция уже заполнена, несколько элементов из решения были исключены (наборы, которые боролись за ту же позицию) и общий вес уменьшилось.