Geek Answers Handbook

Optimal MLB Composition Using Knapsack Option

I am writing a program to find the best MLB range possible using a backpack. To do this, I transfer the data of the player in which the players calculated the cost and salary. Salary will be my "weight" in terms of problems with the backpack.

My problem is not to choose the players, but to choose the most optimal composition. I choose a jug, center, first baseman, second baseman, third baseman, short stop and three outfielders. I can do it all successfully. I want my "weight" to be 36,000, but currently I am choosing a model of only 21,000.

Here is my satchel code:

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

Am I making an obvious mistake that I just don’t see, or is my logic completely disabled?

+6
source share
1 answer

Are you checking the solution correctly? The logic for accepting positions is not included in the backpack logic, which means that the Set solution is a filter on top of the backpack solution. You came to the right decision for the backpack, but because, in addition to the decision, you check whether this position was already filled, several elements were excluded from the set of solutions (elements that fought for the same position) and the total weight decreased.

+1
source

More articles:


All Articles