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:
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($items, 0, $this->capacity);
}
}
$items =
[
new Item(6, 2),
new Item(3, 2),
new Item(5, 6),
new Item(4, 5)
];
$knapsack = new Knapsack(10);
$value = $knapsack->getMaxValue($items);
var_dump($value); // 14
?>
Kommentar