algo:knapsack

[oenone]

Ist das Rucksackproblem ein PHP-Problem?

Nein, aber links unter "Sprachen" stehen C, C++ und PHP

[Benam]

Moin,
ich habe mich als Fachfremder mit viel Interesse durch den Artikel "gekämpft" und kann nicht behaupten, dass er leicht verständlich war (was aber eher an mir als am Autor liegt ).
Ich habe daher eine Frage bezüglich der möglichen Anwendbarkeit auf ein aktuelles Problem. Ich sitze in einer größeren deutschen Handelszentrale und möchte für meinen Warenbereich die Flächen neu (und am besten ideal) verteilen. Ich habe also eine Hauptwarengruppe und mehrere Unterwarengruppen, die ich von den Platzierungsanteilen ideal verteilen will.
Es sind somit vorgegeben: 1.) die größe des Rucksacks (die gesamte zur Verfügung stehende Fläche), und 2.) der Profit je Gegenstand (die Rentabilität der Unterwarengruppen). Das Gewicht in meinem Fall der Platzierungsanteil ist aber nicht vorgegeben (nach dem Motto die Warengruppe X braucht 10m, nehme ich Sie auf oder nicht), sondern ist genau die Variante, die ich ermitteln möchte.
Ist Eurer Meinung nach das Rucksackproblem in abgewandelter Form für diese Problemstellung geignet? Gibt es andere Optimierungsmodelle die Euch bekannt sind, die für meine Problemstellung relevant sein könnten?
Ich würde mich freuen wenn ich ein Feedback erhalten würde.

[nufan]

ich habe mich als Fachfremder mit viel Interesse durch den Artikel "gekämpft" und kann nicht behaupten, dass er leicht verständlich war (was aber eher an mir als am Autor liegt ).

Und wo genau gabs Probleme?

Das Gewicht in meinem Fall der Platzierungsanteil ist aber nicht vorgegeben (nach dem Motto die Warengruppe X braucht 10m, nehme ich Sie auf oder nicht), sondern ist genau die Variante, die ich ermitteln möchte.

Nur um ganz sicher zu gehen, dass ich das auch richtig verstanden habe: Du willst herausfinden, wie viel von jeder Warengruppe du aufnehmen musst, um den Wert zu maximieren?

Ist Eurer Meinung nach das Rucksackproblem in abgewandelter Form für diese Problemstellung geignet?

Wenn ich dein Problem richtig verstanden habe schon

Eine leicht komplexere Version als in meinem Artikel beschrieben, aber doch das gleiche Prinzip. Du hast bestimmt eine Mindestgröße, die du von einer Warengruppe bestellst. Ebenso hast du eine Maximalgröße, die höchstens deine gesamte Fläche sein kann (bzw. die maixmale Menge der Warengruppe, die du bestellen kannst). Nun probierst du für jede Warengruppe jede Fläche zwischen Minimum und Maximum (inklusive) aus.

[Xin]

Es sind somit vorgegeben: 1.) die größe des Rucksacks (die gesamte zur Verfügung stehende Fläche), und 2.) der Profit je Gegenstand (die Rentabilität der Unterwarengruppen). Das Gewicht in meinem Fall der Platzierungsanteil ist aber nicht vorgegeben (nach dem Motto die Warengruppe X braucht 10m, nehme ich Sie auf oder nicht), sondern ist genau die Variante, die ich ermitteln möchte.
Ist Eurer Meinung nach das Rucksackproblem in abgewandelter Form für diese Problemstellung geignet? Gibt es andere Optimierungsmodelle die Euch bekannt sind, die für meine Problemstellung relevant sein könnten?
Ich würde mich freuen wenn ich ein Feedback erhalten würde.

Ich glaube, da fehlt noch was: Die Kaufbereitschaft.

Wenn Du nur nach der Rendite gehst, stellst Du einen Stand mit der größten Rendite an die Kasse, dann müssen sich die Leute nicht bewegen und können direkt auf's Band legen.

Nur ist die Kaufbereitschaft nicht bei allen Kunden gleich. Nicht jeder will Papier mit Facebook-Logo für 38$ kaufen. Auch kommen die Leute nicht in Deinen Laden, wenn sie Mehl kaufen wollen, Du aber Mehl überhaupt nicht anbietest, weil die Rendite Dir zu klein ist.

Du musst quasi zwei Probleme lösen: "Lockangebote", wie Grundnahrungsmittel, die obwohl sie nur eine geringe Rendite haben, die Kaufbereitschaft in Deinem Laden erhöhen und die Leute durch den Laden schicken, so dass sie an den Rendite-Produkten vorbeikommen. Darum stehen Mehl, Milch und Butter ja auch immer hinten im Laden, damit man an den ganzen Regalen vorbei muss. Das muss gekauft werden, hohe Kaufbereitschaft, trotzdem kaum Rendite.

Die restliche Fläche... auch hier gibt es doch mehrere Faktoren. Ein Designer-Händi hat eine hohe Rendite, verbraucht wenig Platz wird aber nur von wenigen Kunden gekauft, weil die Technikfreaks im Saturn einkaufen und sich die Milch von Mama mitbringen lassen. Trotzdem schneidet es besser als ab das Kinderfahrrad: Hohe Rendite, viele Mütter im Laden, leider passen nur vier auf die Euro-Palette. Du brauchst einen Quotienten, der "Kaufwille" mit der Rendite verrechnet. Der Rucksack ist dann die Fläche abzüglich Lockangebote, der Quotient der Wert und der Platzbedarf pro Wert der Platzbedarf im Rucksack.

...falls ich das Problem hier richtig verstehe.


Ist der Rucksack voll und enthält den maximalen Wert guckst Du rein, wofür Du Platz verbraucht hast.

[Benam]

Erstmal vielen Dank für die schnellen Antworten!

Und wo genau gabs Probleme?

Wenn man vor 20 Jahren seinen Mathe LK abgeschlossen hat ist es einfach schwer wieder auf so einer theoretischen Ebene zu denken. Das ist alles

Nur um ganz sicher zu gehen, dass ich das auch richtig verstanden habe: Du willst herausfinden, wie viel von jeder Warengruppe du aufnehmen musst, um den Wert zu maximieren?

Jein.....Ich bin verantwortlich für eine Warengruppe. In meinem Fall Tiefkühlkost. Tiefkühlkost ist in 5 Unterwarengruppen nämlich Obst/Gemüse/Kartoffelprodukte , Fisch , Fertiggerichte / Pizza , Kuchen/Torten und Eis unterteilt. Die Frage ist welche Unterwarengruppe erhält wieviel Prozent der Gesamtfläche, sprich aller Tiefkühltruhen im Markt.

Wenn ich dein Problem richtig verstanden habe schon

Wenn ich dein Problem richtig verstanden habe schon

Eine leicht komplexere Version als in meinem Artikel beschrieben, aber doch das gleiche Prinzip. Du hast bestimmt eine Mindestgröße, die du von einer Warengruppe bestellst. Ebenso hast du eine Maximalgröße, die höchstens deine gesamte Fläche sein kann (bzw. die maixmale Menge der Warengruppe, die du bestellen kannst). Nun probierst du für jede Warengruppe jede Fläche zwischen Minimum und Maximum (inklusive) aus

Ich habe ja Stand heute eine existierende Verteilung der einzelnen Warengruppen. Mit dieser Verteilung erwirtschafte ich unterschiedliche Rentabilitäten je Warengruppe. Die Idee Min- und Maxgrößen zu definieren ist super. Ich würde dann den zwischen dem Min und Maxwert entstehenden neuen Punkten neue Rentabilitäten zuordnen, die ich linear abhängig vom Flächenzuwachs bzw. vom Flächenanbau vom Istwert berechne. Das könnte klappen!!

[Benam]

Ich glaube, da fehlt noch was: Die Kaufbereitschaft.

Es ist sicherlich so, dass eine pareto optimale Verteilung die nur auf der Rentabilität beruht nicht zielführend ist. Den Kunden interessiert es in keinster Form wieviel ich an einem Artikel verdiene. Ihn interessiert, dass ich "seine" Artikel so platziert habe, dass er sie findet und das zu einem Preis den er bereit ist zu bezahlen.

Bei meinem Problem gehe ich aber auch (noch) nicht auf die Artikel ein. Mit welchen Artikel ich die Platzierungsanteile der einzelnen Warenuntergruppen fülle ist dann mein nächstes Problem.

Ich werde allerdings mal überlegen, ob ich dem Platzierungsanteil nicht nur die Rentabilität sondern einen erweiterten Wert entgegen stelle.

[nufan]

Ich hab die Grafiken mit DOT neu erstellt. So ist das ganze leichter wart- und wiederverwendbar. Wenn man die .dot-Dateiendung noch auf die Upload-Whitelist setzt, kann ich die Quelldateien hochladen.

Übrigens verlinkt neben der deutschen (das war ich ^^) auch die russische Wikipedia-Seite auf uns
http://ru.wikipedia.org/wiki/%D0%97%D0% ... 0.BA.D0.B8

[Xin]

Ich hab die Grafiken mit DOT neu erstellt. So ist das ganze leichter wart- und wiederverwendbar. Wenn man die .dot-Dateiendung noch auf die Upload-Whitelist setzt, kann ich die Quelldateien hochladen.

Dot sollte jetzt hochladbar sein, ich habe es hinzugefügt.

Die Dot-Grafiken sehen deutlich professioneller aus

[nufan]

Dot sollte jetzt hochladbar sein, ich habe es hinzugefügt.

Erledigt. Wollen wir die Dateien auch im Artikel verlinken oder reichts wenn wir über die Dateiliste darauf Zugriff haben?

[Xin]

Dot sollte jetzt hochladbar sein, ich habe es hinzugefügt.

Erledigt. Wollen wir die Dateien auch im Artikel verlinken oder reichts wenn wir über die Dateiliste darauf Zugriff haben?

Interessante Frage... eigentlich sollte das reichen, zumal die unkontrollierte Redundanz eher Fehler provoziert. Gleichzeitig geht aber auch das Wissen verloren, dass die .dot Files überhaupt verfügbar sind. Vielleicht sollten wir wenigstens eine Randnotiz machen, wo .dot Files verfügbar sind.
Ansonsten könnte man die auch praktischerweise ins SVN-Repository des Wikis ablegen, also gar nicht unbedingt ins Wiki selbst - schließlich werden sie da gar nicht angezeigt.