Brauche die "Rucksackformel"

[Cyperfriend]

Ich brauche die so genannte Rucksackformel, aber in einer für mich verständlichen Version.

Hintergrund: Ich möchte mir einen so genannten Save-Rechner für ein Browsergame basteln. Hier mal Details:

Ich habe:

RessourceA, RessourceB, RessourceC, RessourceD
SchiffA, SchiffB, SchiffC, SchiffD, SchiffE, SchiffF

Jedes Schiff kostet unterschiedlich viel. Nun will ich die vorhandenen Ressourcen auf den Bau der Schiffe so geschickt aufteilen, dass am Ende möglichst wenig Ressourcen übrig bleiben.

Momentan habe ich ehrlich gesagt noch nicht viel und müsste auch noch lernen die Schiffe in eine Klasse zu packen. Wäre super, wenn mir jemand hilft.


[src=csharp]
public Form1()
{
InitializeComponent();
}

// Ressourcen
ulong RessourceA;
ulong RessourceB;
ulong RessourceC;
ulong RessourceD;

private void cmdErgebnis_Click(object sender, EventArgs e)
{
// Kosten für SchiffA:
RessourceA = 100;
RessourceB = 50;
RessourceC = 30;
RessourceD = 10;
[...]
[/src]

 

[Timon3]

Du könntest entweder den einfacheren Weg gehen und einen Deep-Search-Algorithmus implementieren, was allerdings eine verdammt schreckliche Laufzeit hat. Andererseits könntest du versuchen, das über eine Übergangsmatrix zu gestalten, das sollte relativ sauber sein. Rechne also (RESSOURCENMATRIX) * (ERGEBNISVEKTOR) = (RESSOURCENVEKTOR) und löse das entstehende LGS (linke Seite einfache Matrix*Vektor-Multiplikation, rechte Seite Ergebnisse) auf. Das Lösen kannst du relativ einfach über den entsprechenden Gauß-Algorithmus machen.

http://stackoverflow.com/questions/769/solving-a-linear-equation

 

[Cyperfriend]

Es wird dich vielleicht überraschen (andere die mich hier kennen wohl eher nicht), dass ich von deinem Beitrag exakt gar nichts verstanden habe. Ich muss auch direkt dazu sagen, dass ich in Mathe ne 5 hatte und das auch nur dank Geometrie.

Ich denke in einem ersten Schritt, muss ich die Schiffe alle in eine Klasse packen, damit man damit arbeiten und sie gezielt ansprechen kann. Im zweiten Schritt dann die Rechenformel.

Das Programm muss überhaupt nicht optimal geschrieben sein. Viel wichtiger ist, dass der Programmablauf möglichst verständlich und nachvollziehbar geschrieben wird, so dass ich am Ende auch weis was wo und wie passiert und warum es passiert.

 

[theSplit]

Hm, also ich bin auch bekennender Nichtmathematiker - aber ich würde das Problem so angehen, zumindest das Berechnen, das du von der geringsten Ressource ausgehst und daraus versuchst so viele Schiffe wie möglich zu genererieren.

Ist diese verbraucht und andere Schiffe benötigen diese Ressource nicht würde ich zur nächst kleineren Ressourcen springen, und diese Schritte wiederholen bis diese nicht mehr weiter verwendet werden kann oder aufgebraucht ist. Danach die letzten zwei im gleichen Prinzip auflösen. Wahlweise kannst du auch alle Schiffstypen um jeweils eins erhöhen und ausbalanciert herantasten und dann nur noch herausquetschen was gerade noch möglich ist.

Wäre meine erste Idee zu diesem Problem.

Ist natürlich die Frage welche Schiffstypen nur auf zwei Ressourcen statt vier basieren z.B. - dann müsste man zuerst diese berechnen bzw. immer um eins erhöhen, dann die anderen Typen die vielleicht auch die ein oder andere Ressource benötigt um eins erhöhen.
Also sich versuchen ausbalanciert auf alle Schiffstypen anzunähren.
Übrige Ressourcen werden dann in die kleineren Schiffstypen aufgeteilt, so fern möglich. Aber auch hier würde man vermutlich mit mehr kleinen als großen Schiffen enden, weil der Fokus auf den kleinen anstelle der großen liegt.

Wäre ein zweiter Ansatz.

Hoffe der Gedankengang ist halbwegs verständlich.

 

[TimeCode]

Hi there,

also die ersten Fragen die ich mir stelle, in welcher Art und Weise willst du du dein Browsergame darstellen?!

-Ajax
-Php
-JS
-Flash

?!

Danach würde ich vorschlagen nach einem exakten Beispiel zu suchen welches deine Idee bereits weitgehends wiederspiegelt, das du dieser Idee deine eigene Attribution gibst lassen wir erstmal aussen vor.

Und?! Dein Post klingt mir schon nach Customarbeit/Customwissen. Nichts für ungut
Wärst du bereit Preis X zu bezahlen um deine Idee real zu bekommen ?!
Würdest du Zeit X bereitstellen um das Wissen zu bekommen?!
Welche Priorität hat summa deine Idee?!

Sorry wenns klugscheisserisch klingt, aber dem Preis seiner Idee sollte man immer offen gegenüberstehen.

Cheers TC

 

[Timon3]

@Cyperfriend: Kein Problem, ich kann ja versuchen, es einfacher zu erklären

Erstmal ist es natürlich sinnvoll, ordentliche Schiffs-Objekte zu entwerfen. Probier ein bisschen rum. Was mir am Anfang beim designen guter Klassen geholfen hat war Prototyping, d. h. ich hab meine Klassen soweit es ging vom restlichen Code gelöst neugeschrieben in einer Testumgebung und dann rumprobiert, ob tatsächlich alles abgedeckt ist. Nur mal als Beispiel: Wenn die Schiffs-Klasse die Schiffe auch zeichnen können soll, ist das für deine Tests erstmal nicht nötig. Teste mit separaten, kleinen Codeteilen, ob du die Schiffe z. B. von Hangar zu Hangar bewegen kannst (falls sowas gewünscht ist). Teste, ob du alles grundlegende mit ihnen machen kannst, was du willst. Sobald du die grundlegenden Funktionen abgedeckt hast, kannst du später auch darauf aufbauende Sachen dazuschreiben. So habe ich gelernt, logisch aufgebaute Klassen zu entwickeln.


Dann weiter bzgl. dem Algorithmus: Um in der Mathematik einen Herstellungsprozess darzustellen, verwendet man eine Übergangsmatrix. Du kannst dir das so vorstellen, dass es eine Tabelle ist, bei der die Spalten die Ausgangsprodukte sind und die Zeilen die Ressourcen. Damit kann man ziemlich einfach berechnen, wie viele Ressourcen man braucht, um x Ausgangsprodukte herzustellen. Hierzu gibt es verschiedenste Anleitungen im Internet, die hier hab ich auf YT gefunden und scheint ganz ordentlich zu sein.

Wenn du jetzt deine Prozessmatrix aufgestellt hast, die Beispielsweise so aussehen kann:

	Schiff A	Schiff B	Schiff C
Ressource A	100	50	456
Ressource B	50	30	642
Ressource C	30	110	456
Ressource D	10	485	8656

Kannst du nun relativ einfach bestimmen, wie du deine vorhandenen Ressourcen am effizientesten nutzen kannst. Dafür machst du eigentlich nur das, was ich im Post oben beschrieben habe. Hier hoffentlich nochmal verständlicher erklärt:



Sagen wir, du hast eine 2x3-Matrix, also mit 2 Zeilen und 3 Spalten. Hier bräuchte Schiff A 3x Ressource A und 1x Ressource B, Schiff B braucht 2x Ressource A und Schiff C braucht 1x Ressource A und 2x Ressource B. Dies multiplizierst du mit der Anzahl an Schiffen, die du haben willst, also 1x Schiff A und 4x Schiff B. Dann kommst du rechts auf die Anzahl der Ressourcen, die du brauchst.



Ich weiß, das ist genau andersrum als das was du willst, allerdings soll das nur verdeutlichen, wie Multiplikation zwischen Matrix und Vektor funktioniert (nämlich immer Zeile mal Spalte).



Gehen wir jetzt einmal vom anderen Fall aus: Du hast Ressourcen-Matrix, die dir anzeigt, wie viele Ressourcen du pro Schiff brauchst. Außerdem weißt du, du hast 20x Ressource A und 10x Ressource B. Die Matrix multiplizieren wir jetzt mit unserem gesuchten Vektor, und bekommen den Ressourcenvektor.

(3 1) * (x1, x2) = (20, 10)
(1 2)

Wenn wir die Multiplikationen jetzt aufschreiben, bekommen wir zwei Gleichungen:

3x1 + 1x2 = 20
1x1 + 2x3 = 10

Um dieses LGS zu lösen, gibt es verschiedene Ansätze, jedenfalls kommen wir recht schnell auf das Ergebnis a = 6 & b = 2. Das bedeutet, die effizienteste Nutzungsweise für die oben gegebenen Ressourcen ist 6 Schiffe vom Typ A und 2 Schiffe vom Typ B.


Der Nachteil von diesem Ansatz hier ist, dass auch Kommazahlen rauskommen können als Lösungen, du müsstest dich also um diese Lösungen kümmern. Solange ich nichts übersehe, sollte das hier aber der effizienteste und sauberste Methode sein, deinen Wunsch abzubilden.

 

[theSplit]

Sollte das Ergebnis bei deinem Ressourcenvektor nicht ein anderes sein?

Ich komme da auf 4 und 1 Komma (abgerundet auf 1).

 

[Cyperfriend]

Also STOP.
Ich will KEIN Browsergame programmieren. Ich SPIELE ein solches und es geht darum, dass ich eben meine Ressourcen einsaven will, dass mich niemand angreift, bzw. falls doch diese bereits in den entsprechenden Bauschleifen sind und der Gegner nicht dran kommt.

Hier mal ein Beispiel eines solchen Save-Rechners aus dem Spiel EarthLost
http://www.el-tools.at/index.php?section=toolSaven
Klickt oben einfach alle Kästchen an und kopiert in die Textbox einfach mal folgendes und klickt auf "Zum Weltuntergang"

500000000m 2500000000m 10000000m 5000000m 1000000m

Danach sieht man, was man am besten bauen sollte um möglichst wenig Rohstoffe übrig zu haben, also sie werden optimal aufgeteilt. Sowas will ich eben für das andere Browsergame, welches ich spiele auch, nur dass dort das Saven über die Schiffsbauschleife geschieht.

Haben möchte ich das Ganze als C# Projekt.

 

[drfuture]

@Cyberfriend alle außer TimeCode haben das schon verstanden - dem seine Posts kann man zu 100% mit gutem Gewissen ignorieren

 

[keinbenutzername]

Sorry wenns klugscheisserisch klingt, aber dem Preis seiner Idee sollte man immer offen gegenüberstehen.

nein, klingt gar nicht klugscheisserisch da (ich zumindest) klugscheisserisch so definiere, dass jemand Ahnung hat und dies anderen unter die Nase reibt.

@topic
so wie ich das sehe will cyberfriend da am besten code in C# sehen. Würde mich auch interessieren.

 

[Skipjack]

Der Nachteil von diesem Ansatz hier ist, dass auch Kommazahlen rauskommen können als Lösungen

Ich fürchte, genau das ist das Problem. Allgemein werden die Lösungen wohl immer Reell - also Kommazahlen sein. Du nimmst hier an, dass (Ab)runden dann zur optimalen ganzzahligen Lösung führen würde. Je komplexer das Gleichungssystem ist, desto eher wird das wohl nicht der Fall sein.

Eigentlich ist die Problemstellung ja eine andere:
Finde eine ganzzahlige Lösung X = (x1, x2, ...) für die delta
Resourcenmatrix * X - Ressourcen >= delta >= 0
minimal wird.

Eine - recht einfach zu programmierende - Lösung wäre ein stochastischer Optimierungsalgorithmus.
Du brauchst eine Akzeptanzgrenze epsilon, ab der Du mit einer Lösung zufrieden bist (etwas Resourcen werden wohl meistens übrig bleiben)
1) Wähle zufällig ein X -> X_0
2) Berechne delta
3) Falls delta <= epsilon, fertig
4) Variiere eine Komponente von X (wähle dazu zufällig eine Komponente aus und mach - ebenfalls zufällig - ein +/-1)
Das ist das neue X
5) Berechne delta für dieses X und wenn kleiner als vorher weiter bei 3, sonst zurück zu 4

Nicht vergessen, ein Abbruchkriterium bei 4 einzubauen, wenn alle möglichen Variationen zu keiner Verbesserung geführt haben.
Epsilon könnte am Anfang 0 sein und erst mit steigender Suchdauer erhöht werden.
Man könnte (sollte) obigen Algorithmus mehrere Male mit verschiedenen Startwerten X_0 durchführen und die gefundenen Ergebnisse vergleichen.
Ein Durchlauf findest schliesslich nur ein lokales Minimum, welches vom absoluten abweichen kann.

 

[BurnerR]

Jedenfalls schreibt man bei solchen Aufgaben zu erst den Algorithmus in Pseudo-Code auf und erst danach implementiert man ihn in der gewünschten Programmiersprache.