Was ist das für eine Variante des Rucksackproblems?

Hi,

Ich hab folgende Problemstellung:
Ein Rucksack mit einem Fassungsvermögen von W einheiten (is egal was für ne einheit )
jetzt hab ich mehrer Gegenstände G1,G2,G3...Gn, die alle eine bestimmte Menge an Einheiten im Rucksack benötigen. Alle passen nicht rein und jeder soll höchstens 1. mal reingemacht werden. Es gibt kein Profit wie beim originalen Rucksackproblem, jeder Gegenstand ist gleichwertig. Jetzt suche ich einen Algorithmus der ohne Bruteforce die bestmögliche Füllung des Rucksacks mit den Gegenständen rausbekommt. Also, der das Fassungsvermögen so gut wie möglich Ausschöpft. Es können auch Gegenstände übrig bleiben, hauptsache es wird so viel Fassungsvermögen wie möglich benutzt.
Bei 10 Gegenstände würde das mit Bruteforce (also alle Möglichkeiten ausprobieren) ja noch gehen, aber bei mehrern 100 wären das ja schon zielich viele Berechnungen.

Gefunden habe ich dazu natürlich erst mal das Rucksack-problem, aber da wird mit Profit gerechnet. Dann das Change-Making Problem, aber da dürfen Gegenstände (Münzen) mehrmals verwendet werden. Und ein Code-Beispiel hab ich für beides noch nicht wirklich gefunden.

Gibt es denn genau für mein Problem auch einen Namen? oder hat sogar jemand nen Algorithmus dafür?

Gruß
MaN_

Entschuldige, aber wenn alle deine Gegenstände denselben Wert haben, dann ist das doch einfach:

Benutz die Lösung, die du für das Rucksackproblem hast, und verwende immer dieselbe Wertigkeit. Letztlich ist das nur ein Sonderfall.

Zum Rucksackproblem siehe auch http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php

Gruss
Sid

sie haben alle den gleichen Profit. Den gleichen Wert an Einheiten natürlich nicht.

Jau. Das meinte ich auch.

Die Sache ist die: Wenn alle Gegenstände den gleichen WERT (50 Mark) aber unterschiedliche GRÖßE (2 Kubikmeter, 3 Kubikmeter...) haben, und du ein Behältnis einer bestimmten GRÖßE hast (20 Kubikmeter) dann suchst du eigentlich auch nur nach dem größtmöglichen WERT, den du mitnehmen kannst. Das die Gegenstände an sich alle den gleichen WERT haben, ist unerheblich, die Lösung optimiert ja den Gesamt-WERT, und damit, in deinem Fall, AUTOMATISCH auch die Größe.

Oder ich bin komplett auf dem Holzweg?

Siehe auch:
http://www.or.deis.unibo.it/knapsack.html

[quote="Sid2K6"]Jau. Das meinte ich auch.

Die Sache ist die: Wenn alle Gegenstände den gleichen WERT (50 Mark) aber unterschiedliche GRÖßE (2 Kubikmeter, 3 Kubikmeter...) haben, und du ein Behältnis einer bestimmten GRÖßE hast (20 Kubikmeter) dann suchst du eigentlich auch nur nach dem größtmöglichen WERT, den du mitnehmen kannst. Das die Gegenstände an sich alle den gleichen WERT haben, ist unerheblich, die Lösung optimiert ja den Gesamt-WERT, und damit, in deinem Fall, AUTOMATISCH auch die Größe.
/quote]

genau das ist es!

Jetzt stellt sich für mich nur die Frage (nach 3. mal lesen des links http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo15.php )

Wie geht das in meinem fall? Was sind bei mir die Pareto-optimalen Punkte? Ich hab ja kein Profit.

sag' nochmal genau, was das ziel ist: möglichst viele gegenstände reinzubekommen, oder möglichst wenig leeren platz übrig zu haben?

möglichst wenig leeren Platz übrig zu haben.

So funktioniert das nicht - wenn die Gegenstände alle den selben
Wert haben, landen automatisch die kleinen bevorzugt drin, da dort
die "Wertdichte" höher ist. Entweder Du musst das gewichten
(1 kg -> Wert 1, 2 kg -> Wert 2, 5 kg ->Wert 5) oder Du
betrachtest das ganze als Subset-Sum Problem.

Gruss,

Stefan

Bashar

MaN_ schrieb:

möglichst wenig leeren Platz übrig zu haben.

Dann soll also der belegte Platz maximiert werden? Dann ist der Wert jeweils gleich dem Platzverbrauch.