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} ?
Ankündigung
Einklappen
Keine Ankündigung bisher.
Gleichmäßiges teilen von Array's
Einklappen
Neue Werbung 2019
Einklappen
X
-
Gast
-
Häufchen machen
Zitat von xm22 Beitrag anzeigenBeide Arrays sollen die selbe, möglichst niedrige Summe aus den Elementen des Ursprungsarrays bilden.
Zitat von fab Beitrag anzeigen
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
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 (5, 5, 4, 3, 3),
// two valid solutions
array (3, 1, 1, 2, 2, 1),
// one possible solution [6, 5], [4, 3, 2, 1, 1]
array (1, 1, 2, 3, 4, 5, 6),
);
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]))
);
}
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.
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
...Wenn man die Wurst schräg anschneidet, hält sie länger, weil die Scheiben größer sind.
Kommentar
Kommentar