Ankündigung

Einklappen
Keine Ankündigung bisher.

Gleichmäßiges teilen von Array's

Einklappen

Neue Werbung 2019

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

  • #16
    Beide Arrays sollen die selbe, möglichst niedrige Summe aus den Elementen des Ursprungsarrays bilden. Aber was passiert, wenn das nicht möglich ist, z. B. {1, 3} ?

    Kommentar


    • #17
      Häufchen machen

      Zitat von xm22 Beitrag anzeigen
      Beide Arrays sollen die selbe, möglichst niedrige Summe aus den Elementen des Ursprungsarrays bilden.
      Nicht ganz. Die Differenz der beiden Teilsummen soll möglichst nahe 0 liegen.

      Sehr schön. Endlich eine klar verständliche Beschreibung des Problems.

      Lässt sich wohl mit dynamischer Programmierung lösen (siehe Link) aber das ist etwas für hartgesottene theoretische Informatiker. Jetzt wo du einen Namen dafür hast, findest du vielleicht auch etwas fertiges
      Der entsprechende Artikel in der englischsprachigen Wikipedia bietet diverse Algorithmen an. Da ich weder theoretisch hartgesotten genug bin, noch praktisch den dort angegebenen Pseudocode der (DP-)Lösung vollständig verstanden habe (das Laufzeitverhalten ist zusätzlich abschreckend), hier die einfachste Lösung des naiven Greedy-Algorithmus' (mit allen seinen aufgeführten Fehlern):

      PHP-Code:
      class partitionfinder {

          
      // see: http://en.wikipedia.org/wiki/
          // Partition_problem#The_greedy_algorithm

          /// return array (partition, partition)
          
      static function greedy(
              Array 
      $list /// array() of numbers (int or dbl)
          
      ) {
              
      rsort($list);

              
      $a = array ();
              
      $b = array ();
              
      // providing an explicite sum should be a bit faster
              // than calling array_sum() for every iteration
              
      $sum_a 0
              
      $sum_b 0
              foreach (
      $list as $num) {
                  if (
      $sum_a $sum_b) {
                      
      $a[] = $num;
                      
      $sum_a += $num;
                  }
                  else {
                      
      $b[] = $num;
                      
      $sum_b += $num;
                  }
              }
              return array (
      $a$b);
          }

      }

      $tests = array (
          
      // best solution [5, 5], [4, 3, 3]
          
      array (55433), 
          
      // two valid solutions
          
      array (311221), 
          
      // one possible solution [6, 5], [4, 3, 2, 1, 1]
          
      array (1123456),
      );

      foreach (
      $tests as $test) {
          
      $partitions partitionfinder::greedy($test);
          
      var_dump($test);
          
      var_dump($partitions);
          
      printf(
              
      'diff: %s',
              
      abs(array_sum($partitions[0]) - array_sum($partitions[1]))
          );

      Die anderen Algorithmen überlasse ich dem interessierten Leser als Übungsaufgabe.
      Eventuell würde ich mir die Sache aber auch selbst nochmal näher anschauen, wenn mir wer eine praktische Anwendung für das Problem nennen könnte.

      Zitat von nikosch Beitrag anzeigen
      ...
      Ich sehe jetzt gerade nicht, wo Deine Frage ein Sortierproblem ist.
      Wenn man das Problem intuitiv angeht, kommt man auf eben diese (naive) Lösung. Zumindest ging mir das so, bevor ich den Wikipedia-Artikel gelesen hatte. Dafür benötigt man die Ausgangs-Liste sortiert (von groß nach klein). Auch andere Lösungsansätze profitieren von einer Vorsortierung.

      Was das jetzt allerdings mit Bucket-Sort zu tun haben soll, verstehe ich auch nicht. Für PHP-Arrays gibts nunmal nur das eingebaute Quicksort.

      Zitat von bastofa Beitrag anzeigen
      ...
      werte = 1,1,2,3,4,5,6

      spalte 1 wäre dann z.B. 6,5
      und spalte 2 dann 1,1,2,3,4
      ...
      Der Greedy-Algo bekommt [5, 4, 1, 1] und [6, 3, 2] heraus. Die Differenz der Teilsummen ist aber auch hier 0.
      Wenn man die Wurst schräg anschneidet, hält sie länger, weil die Scheiben größer sind.

      Kommentar

      Lädt...
      X