Knapsack varyantı kullanarak en uygun MLB dizisi

Question

Bir sırt çantası çözümü kullanarak mümkün olan en iyi MLB dizisini bulmak için bir program yazıyorum. Bunun için bir oyuncu değeri ve maaşı olan oyuncu verilerine geçiyorum. Maaş bir sırt çantası problemi olarak benim "ağırlık" olacaktır.

Sorunum, oyuncuları seçemiyor, bunun yerine en uygun programı seçiyor. Ben bir sürahi, bir merkez, ilk üstat, ikinci üstat, üçüncü üstat, kısa durak ve üç outfielder seçiyorum. Bunu başarılı bir şekilde yapabilirim. "Ağırlığımın" 36.000 olmasını istiyorum, ancak şu anda sadece 21.000 ile bir sıralama seçiyorum. İşte

sırt çantam kodudur:

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

ben sadece göremiyorum bariz hata yapma muyum, ya da benim mantık tamamen kapalı?

Answer 1

SolutionSet'i doğru mu kontrol ediyorsunuz? Pozisyonları kabul etmek için kullanılan mantık, sırt çantası mantığına dahil değildir, bu da solutionSet'in sırt çantası çözümünün üstünde bir filtre olduğu anlamına gelir. Doğru sırt çantası çözümüne ulaştınız, ama çözümün üstünde, konumun doldurulmuş olup olmadığını kontrol ediyorsunuz, çünkü bir kaç madde çözelti setinden (aynı pozisyon için savaşıyorlardı) ve toplam ağırlıktan yok edildi. azalmıştır.