Tôi đang viết chương trình để tìm dòng sản phẩm MLB tốt nhất có thể sử dụng giải pháp ba lô. Đối với điều này tôi vượt qua trong dữ liệu cầu thủ trong đó có một cầu thủ tính toán giá trị và tiền lương. Tiền lương sẽ là "trọng lượng" của tôi về vấn đề một chiếc ba lô.Dòng sản phẩm MLB tối ưu sử dụng biến thể Knapsack
Sự cố của tôi không thể chọn người chơi, mà là chọn đội hình tối ưu nhất. Tôi đang chọn một bình, một trung tâm, baseman đầu tiên, baseman thứ hai, baseman thứ ba, dừng ngắn, và ba outfielders. Tôi có thể làm tất cả điều này thành công. Tôi muốn "trọng lượng" của tôi là 36.000, nhưng hiện tại tôi chỉ chọn một dòng sản phẩm với tổng số là 21.000.
Đây là mã ba lô của tôi:
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};
};
Tôi có làm một sai lầm hiển nhiên rằng tôi chỉ không nhìn thấy, hoặc là logic của tôi hoàn toàn tắt?
Bạn có thể chia sẻ một số dữ liệu mẫu không? Và cũng có thể là một fiddle? –