使用背包变体算法得出最佳MLB阵容

Question

使用背包变体算法得出最佳MLB阵容

javascriptmultidimensional-arrayknapsack-problem

7

我正在编写一个程序，使用背包问题的解决方案来找到最佳的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};
};

我是否犯了一个显而易见的错误，却没有看到它，或者我的逻辑完全是错的？

- urnotsam

你能分享一些样本数据吗？还有一个fiddle（在线代码编辑器）吗？ - Bhargav Ponnapalli

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bhargav Ponnapalli · Accepted Answer

你正在检查solutionSet，对吗？接受位置的逻辑不包含在背包逻辑中，这意味着solutionSet是基于背包解决方案的筛选器。你已经得出了正确的背包解决方案，但因为在解决方案之上，你正在检查位置是否已经填充，所以一些物品从solutionSet中被排除（这些物品争夺同一个位置），总重量减少了。