Multiknapsack-Algorithmus - außerhalb der Sammlung beim Versuch, Objekt zu entfernen

Question

Ich habe das Problem bei der Arbeit an meinem Multiknapsack Solver festgestellt. Das Programm funktioniert gut auf einem Rucksack, aber wenn es um mehrere Knaps geht, gibt es einige Probleme.

Problem: Die Artikel werden nicht aus der Sammlung entfernt. Ich weiß, dass ich brauche, dies zu tun, weil für den zweiten Tornister seiner wieder durch die gleichen Objekte laufen - so die maximierte val ist die gleiche ...

private void Knapsack() 
{ 
    List<Plecak> descendingKanps = _plecakList.OrderByDescending(o => o.W).ToList(); // List of configured Kanpsacks in descending order 
    List<Produkt> descendingProducts = _produktList.OrderByDescending(o => o.cena).ToList(); // List of products to pack in descending order 
    int N = descendingProducts.Count; //number of items in product list 
    double maxVal = 0; // accumulated value of one knapsack 
    foreach (Plecak p in descendingKanps) // for every knapsack... 
    { 
     double[,] V = new double[N + 1, (int)p.W + 1]; //array that stores best option (the value of item) 
     for (int c = 0; c <= p.W; c++) //since its a 0-1 MKP problem so initialize whole array with zeroes 
     { 
      V[0, c] = 0; 
     } 
     for (int r = 0; r <= N; r++) 
     { 
      V[r, 0] = 0; 
     } 

     for (int i = 1; i <= N; i++) // constraint of items count 
     { 
      for (int wt = 1; wt <= p.W; wt++) //the constraint of weight 
      { 
       if (descendingProducts[i - 1].waga < wt + 1) // if weight of the product is less than constraint, so it can be added... 
        V[i, wt] = Math.Max(descendingProducts[i - 1].cena + V[i - 1, wt - descendingProducts[i - 1].waga], V[i - 1, wt]); // find best solution and add the value to the Value array, comapre the value with the value form previous row 
       else 
        V[i, wt] = V[i - 1, wt]; // keep 0, or last best solution 

       maxVal = V[i, wt]; // assign to variable 
      } 
     } 
     summary.Items.Add("maximum val for knapsack: " + p.nazwa + " is: " + maxVal); // print out the value of knapsack 
    } 
} 

Answer 1

Das wird mich hoffentlich wiederum in eine Antwort, aber jetzt Es ist eine Frage.

In Ihrem Code haben Sie dies:

for (int c = 0; c <= p.W; c++) //since its a 0-1 MKP problem so initialize whole array with zeroes 
{ 
    V[0, c] = 0; 
} 
for (int r = 0; r <= N; r++) 
{ 
    V[r, 0] = 0; 
} 

Sie sagen, dass Sie "mit Nullen ganze Array initialisieren". Der obige Code wird dies für ein Array tun:

 
0 0 0 0 0 
0 1 1 1 1 
0 1 1 1 1 
0 1 1 1 1 

Sie werden nur die erste Spalte und die oberste Zeile erreichen. Wenn alle Orte in der Anordnung sollte 0 geändert werden, dann ist dies der richtige Ansatz:

for (int r = 0; r <= N; r++) 
{ 
    for (int c = 0; c <= p.W; c++) 
    { 
     V[r, c] = 0; 
    } 
} 

ich diese Eingabe hoffen von Hilfe sein kann.