Ankündigung

Einklappen
Keine Ankündigung bisher.

Rucksackproblem

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • Rucksackproblem

    Ich habe gestern einen Algorithmus zum Rucksackproblem implementiert. 2 Sachen finde ich dabei seltsam.

    Der erste der beiden Punkte:

    Warum müssen bei einer dynamischen Programmierung die Gewichte ganzzahlige Werte sein? So wie ich das sehe, werden die Gewichte einfach immer nur weiter von der Kapazität subtrahiert.

    Bei mir schaut die Programmierung folgendermaßen aus:
    PHP-Code:
    <?php
       error_reporting
    (~0);
       
       class 
    Item
       
    {
          private 
    $value
          private 
    $weight
          
          
    /**
           * @param number $value >= 0 Wert
           * @param number $weight >= 0 Gewichtseinheiten
           */
          
    function __construct($value$weight)
          {
             
    $this->value $value;
             
    $this->weight $weight;
          }
          function 
    getValue()
          {
             return 
    $this->value;
          }
          function 
    getWeight()
          {
             return 
    $this->weight;
          }
       }
       
       class 
    Knapsack
       
    {
          private 
    $capacity;
          
          
    /**
           * @param number $capacity erlaubtes Maximalgewicht
           *    >= 0 Gewichtseinheiten
           */
          
    function __construct($capacity)
          {
             
    $this->capacity $capacity;
          }
          
    /**
           * @param array $items Gegenstände (Item-Instanzen)
           * @param int $i Index des Gegenstands.
           *    0 <= i < Anzahl Gegenstände 
           * @param number $restCapacity Wie viel Gewicht der Rucksack noch aufnehmen kann.
           */
          
    private function recGetMaxValue(array &$items$i$restCapacity)
          {
             if(
    $i == count($items) - 1// Kontrolle, ob letzter Gegenstand
             
    {
                if(
    $restCapacity $items[$i]->getWeight())
                {
                   return 
    0;
                }
                return 
    $items[$i]->getValue();
             }
             
             if(
    $restCapacity $items[$i]->getWeight())
             {
                return 
    $this->recGetMaxValue($items$i 1$restCapacity); // linke Seite (nächsten Gegenstand NICHT einpacken)
             
    }
             return 
    max
             
    (
                
    $this->recGetMaxValue($items$i 1$restCapacity), // linke Seite (nächsten Gegenstand NICHT einpacken)
                
    $this->recGetMaxValue($items$i 1$restCapacity $items[$i]->getWeight()) + $items[$i]->getValue() // rechte Seite (nächsten Gegenstand einpacken)
             
    );
          }
          
    /**
           * Liefert den max. Wert der eingepackten Gegenstände unter Berücksichtigung des erlaubten Maximalgewichts.
           * Es liefert jedoch keine Informationen darüber, welche Gegenstände eingepackt werden sollen.
           * @return array $items Gegenstände (Item-Instanzen)
           * @return number Maximaler Wert eingepackter Gegenstände.
           */
          
    function getMaxValue(array &$items)
          {
             return 
    $this->recGetMaxValue($items0$this->capacity);
          }
       }
       
       
    $items =
       [
          new 
    Item(62),
          new 
    Item(32),
          new 
    Item(56),
          new 
    Item(45)
       ];
       
    $knapsack = new Knapsack(10);
       
    $value $knapsack->getMaxValue($items);
       
    var_dump($value); // 14
    ?>


  • #2
    Warum müssen bei einer dynamischen Programmierung die Gewichte ganzzahlige Werte sein
    müsssen sie das?
    und die zweite frage?

    Kommentar


    • #3
      Verdammt, ich habe da einiges durcheinandergebracht! Die Frage 1 einfach vergessen.

      Jetzt der zweite Punkt, der mich verwirrt.

      Das Programm liefert mir eine Gewichtsangabe zurück. Und zwar das Gewicht jener Produkte, die man am Besten in den Rucksack packt. Ich verstehe nicht, was mir dieser Wert bringen soll. Mich interessiert doch überhaut nicht das Gewicht, das der Rucksack dann hat. Ich will doch nur wissen, welche Gegenstände ich in den Rucksack reingeben soll. Und alleine aufgrund der Info zum Gesamtgewicht kann ich doch unmöglich auf die Gegenstände schließen, die ich in den Rucksack reingeben soll, oder?

      Kommentar


      • #4
        Hmm, Du hast den Code "implementiert", aber verstehst überhaupt nicht, wie er funktioniert? Klar...
        --

        „Emoticons machen einen Beitrag etwas freundlicher. Deine wirken zwar fachlich richtig sein, aber meist ziemlich uninteressant.
        Wenn man nur Text sieht, haben viele junge Entwickler keine interesse, diese stumpfen Texte zu lesen.“


        --

        Kommentar


        • #5
          Kannst du den Items nicht etwas zur Identifikation mitgeben?
          Relax, you're doing fine.
          RTFM | php.de Wissenssammlung | Datenbankindizes | Dateien in der DB?

          Kommentar


          • #6
            shit // TE un nichrt TE verwechselt: pause.

            Kommentar


            • #7
              Du hast also was (Code) geschrieben, das nicht dein Problem löst
              Der Algorithmus ist eben darauf ausgelegt, den maximalen Wert zurückzugeben (übrigens, WERT, nichtt GEWICHT ). Wenn du was anderes brauchst, musst du den anders formulieren.

              Kommentar


              • #8
                Kannst du den Items nicht etwas zur Identifikation mitgeben?
                Die Items sind sowieso eindeutig, da jedes Item eine eigene Instanz der Klasse ist.
                (übrigens, WERT, nichtt GEWICHT
                Oh, entschuldigung, du hast natürlich recht.
                Wenn du was anderes brauchst, musst du den anders formulieren.
                Wie würdest du das lösen? Es könnte schließlich mehrere Lösungsvarianten geben.

                Kommentar


                • #9
                  Zitat von moma Beitrag anzeigen
                  ich? mal schauen.
                  ?
                  Relax, you're doing fine.
                  RTFM | php.de Wissenssammlung | Datenbankindizes | Dateien in der DB?

                  Kommentar


                  • #10
                    shit // TE un nichrt TE verwechselt: pause.
                    Kann passieren. Nach der gestrigen Aktion mit diesem Algorithmus bin ich auch nicht ganz auf der Höhe.

                    Wie wärs, wenn recGetMaxValue zusätzlich auch noch ein 2-dimensionales Array zurückliefert. Jedes Arrayelement stellt dann eine Lösungsmenge für den jeweiligen Subtree dar. Jede Lösungsmenge besteht aus jenen Items, die für den Subtree eine optimale Lösung bilden. Dort wo der max-Befehl steht, entscheide ich dann, ob ich das 2-dimensionale Array vom rechten oder vom linken Subtree nehme. Liefern mir beide Subtrees gleich gute Ergebnisse, merge ich die beiden 2-dimensionalen Arrays.

                    Die Methode getMaxValue würde dann nur noch das 2-dimensionale Array zurückgeben. Sollte ich dann immer noch wissen wollen, wie wertvoll der Inhalt ist, oder wie schwer die unterschiedlichen Lösungsvarianten sind, kann ich das immer noch leicht mittels einer Summenbildung ermitteln.

                    Kommentar


                    • #11
                      Ja, das hört sich doch gut an. Warum programmirest du das dann nicht?

                      Kommentar


                      • #12
                        Ja, das hört sich doch gut an. Warum programmirest du das dann nicht?
                        Werd ich dann etwas später versuche, falls nicht noch wer eine bessere Idee dazu hat. Momentan bin ich noch nicht fit genug dafür. Diese Algorithmen schaffen mich echt total.

                        Kommentar


                        • #13
                          PHP-Code:
                          <?php
                             error_reporting
                          (~0);
                             
                             class 
                          Item
                             
                          {
                                private 
                          $value
                                private 
                          $weight
                                
                                
                          /**
                                 * @param number $value >= 0 Wert
                                 * @param number $weight >= 0 Gewichtseinheiten
                                 */
                                
                          function __construct($value$weight)
                                {
                                   
                          $this->value $value;
                                   
                          $this->weight $weight;
                                }
                                function 
                          getValue()
                                {
                                   return 
                          $this->value;
                                }
                                function 
                          getWeight()
                                {
                                   return 
                          $this->weight;
                                }
                             }
                             
                             class 
                          Knapsack
                             
                          {
                                private 
                          $capacity;
                                
                                
                          /**
                                 * @param number $capacity erlaubtes Maximalgewicht
                                 *    >= 0 Gewichtseinheiten
                                 */
                                
                          function __construct($capacity)
                                {
                                   
                          $this->capacity $capacity;
                                }
                                
                          /**
                                 * @param array $items Gegenstände (Item-Instanzen)
                                 * @param int $i Index des Gegenstands.
                                 *    0 <= i < Anzahl Gegenstände 
                                 * @param number $restCapacity Wie viel Gewicht der Rucksack noch aufnehmen kann.
                                 * @return array
                                 *    ['value'] number Maximaler Wert eingepackter Gegenstände für einen bestimmten Subtree.
                                 *    ['items'] array Liste an optimalen Lösungen für einen bestimmten Subtree.
                                 *       Jede Lösung besteht aus einer Menge an Gegenständen (Item-Instanzen).
                                 */
                                
                          private function recGet(array &$items$i$restCapacity)
                                {
                                   if(
                          $i == count($items) - 1// Kontrolle, ob letzter Gegenstand
                                   
                          {
                                      if(
                          $restCapacity $items[$i]->getWeight())
                                      {
                                         return 
                                         [
                                            
                          'value' => 0
                                            
                          'items' => []
                                         ];
                                      }
                                      
                          $result = [];
                                      
                          $result[] = [$items[$i]];
                                      return 
                                      [
                                         
                          'value' => $items[$i]->getValue(), 
                                         
                          'items' => $result
                                      
                          ];
                                   }
                                   
                                   if(
                          $restCapacity $items[$i]->getWeight())
                                   {
                                      return 
                          $this->recGet($items$i 1$restCapacity); // linke Seite (nächsten Gegenstand NICHT einpacken)
                                   
                          }
                                   
                                   
                          $left $this->recGet($items$i 1$restCapacity); // linke Seite (nächsten Gegenstand NICHT einpacken)
                                   
                          $right $this->recGet($items$i 1$restCapacity $items[$i]->getWeight()); // rechte Seite (nächsten Gegenstand einpacken)
                                   
                          $right['value'] += $items[$i]->getValue();
                                   if(
                          $right['value'] < $left['value'])
                                   {
                                      return 
                          $left// auf der linken Seite kommt kein Gegenstand hinzu
                                   
                          }
                                   
                          // rechts Gegenstand hinzufügen:
                                   
                          if(count($right['items']) > 0)
                                   {
                                      foreach(
                          $right['items'] as &$rightItems)
                                      {
                                         
                          $rightItems[] = $items[$i];
                                      }
                                   }
                                   else
                                   {
                                      
                          $right['items'][] = [$items[$i]];
                                   }
                                   if(
                          $right['value'] == $left['value'])
                                   {
                                      
                          // Sind beide Seiten gleich gut, müssen müssen alle bestmöglichen Lösungen zusammengefügt werden:
                                      
                          $right['items'] = array_merge($left['items'], $right['items']);
                                   }
                                   return 
                          $right;
                                }
                                
                          /**
                                 * Liefert alle optimalen Lösungen.
                                 * @param array $items Gegenstände (Item-Instanzen)
                                 * @return array Liste an optimalen Lösungen.
                                 *    Jede Lösung besteht aus einer Menge an Gegenständen (Item-Instanzen).
                                 */
                                
                          function get(array &$items)
                                {
                                   return 
                          $this->recGet($items0$this->capacity)['items'];
                                }
                             }

                             
                          $items =
                             [
                                new 
                          Item(62),
                                new 
                          Item(32),
                                new 
                          Item(56),
                                new 
                          Item(45)
                             ];
                             
                          $knapsack = new Knapsack(10);
                             
                          $value $knapsack->get($items);
                             
                          var_dump($value);
                          ?>
                          Ist das OK, oder gibts noch eine bessere Lösung?

                          Kommentar


                          • #14
                            PHP-Code:
                            if($i == count($items) - 1// Kontrolle, ob letzter Gegenstand
                            {
                               if(
                            $restCapacity $items[$i]->getWeight()) 
                            Kann dieser Fall eigentlich irgendwann eintreten? In meinem Buch wird im Algorithmus dieser Fall berücksichtigt. Aber mir kommt das etwas seltsam vor.

                            EDIT: Frage hat sich erledigt, habe einen Fall gefunden.

                            Kommentar

                            Lädt...
                            X