Brauche Hilfe bei einer Aufgabe in Delphi

[nightwarrior]

Hallo

Brauche unbedingt Hilfe bei einer Aufgabe in Informatik !!!
Ich muss bis Mitte November ein Programm in Delphi oder Pascal geschrieben haben! Leider habe ich sehr schlechte Kenntnisse in Delphi kann allerhöchstens mal ein Programm schreiben mit dem ich 2 Zahlen addieren kann .

Hier einmal die Aufgabe:

Närrische Wirtschaft

Ein Karnevalsverein nimmt monatlich €1000 an Mitgliedsbeiträgen ein. Davon will der Verein
verschiedene Anschaffungen tätigen. Leider ist der Schatzmeister an unangenehme närrische Regeln gebunden: Er kann monatlich bis zu €1000 ausgeben. Gibt er weniger aus, wird für den Rest Eis gekauft; sein Budget für den nächsten Monat ist dann leider wieder nur €1000, da ja der Rest für Eisessen verschwendet wurde. Er möchte nun zunächst Gegenstände mit folgenden Preisen kaufen:
€340,
€670,
€790,
€1320,
€2100 und
€5200.

Es sieht so aus, als hätte er keine Chance, die letzten drei Gegenstände zu besorgen. Zum Glück kann er sich mit einem erlaubten Trick behelfen: Er hat gute Beziehungen zum Geschäft, in welchem er alle Einkäufe zu tätigen gedenkt. Der Verkäufer ist stets bereit, bereits verkaufte Gegenstände zurückzunehmen und dafür andere Gegenstände entsprechend billiger zu verkaufen. Hat der Schatzmeister beispielsweise schon Gegenstände im Werte von €800 und €1100, so kann er diese zurückgeben, €900 zuzahlen und auf diese Weise einen Gegenstand für €2800 erwerben, ohne das monatliche Budget zu überschreiten. Tatsächlich kann er durch geschicktes Handeln alle sechs gewünschten Gegenstände in 13 Monaten beschaffen.

Aufgabe
Schreibe ein Programm, das Menschen in ähnlicher Situation helfen kann. Es soll zunächst das monatliche Budget und die Preise aller Gegenstände einlesen. Dann muss es berechnen, welche der Gegenstände besorgt werden können, und einen Plan ausgeben, welche Gegenstände in jedem Monat gekauft beziehungsweise zurückgegeben werden sollen. Dabei muss eine kleinst mögliche Anzahl von Monaten verwendet werden. Lasse Dein Programm mit den Daten des Karnevalsvereins laufen.

Bin über jede Hilfe dankbar

MFG Night

[terra-power]

Man müsste sich erstmal schnell überlegen ob das problem überhaupt effizient mit einem algorithmus lösbar ist. Auf den ersten Blick sieht es nämlich dem Rucksackproblem ähnlich und das würde brute force bedeuten. Die implementierung ist erstmal zweitranig. Man müsste sich erstmal überlegen ob man alle lösungen, eine lösungen oder eine approximation erreichen will. Dann spielt man das ganze auf dem papier durch und programmiert es...

wenn ich am wochenende zeit habe, versuche ich mal ne kleine lösung.

[terra-power]

Boah, dass ist ja mies. Du bearbeitest eine Aufgabe bis Mitte November (13. 11.2006 um genau zuz sein) um damit beim Informatiker Wttbewerb weiter zu kommen. Das war doch verboten, wenn ich mich recht entsinne. Naja, egal.. auf jedenfall wirst du von mir keine Hilfe bekommen. Solche unehrlichkeit, werde ich nicht belohnen.

Schade, dass ich nicht mehr teilnehmen kann, hatte die Lösung schon fertig ... :-(

[nightwarrior]

@ terra-power

ich nehme gar nicht an diesem Wettbewerb teil, dass ist die Aufgabe die uns unser Lehrer gegeben hat. Was würde mir das nutzen wenn ich die Aufgabe hätte wenn ich dort Teilnehmen würde? Kenne mich ja noch net so gut in Delphi aus und dann soll ich bei einem Wettbewerb mitmachen * lool *. Die würden mich auslachen ^^!!!

Also nochmal diese Aufgabe ist von diesem Wettbewerb, das stimmt aber weil die noch aktuell ist kann keiner die Lösung im Internet finden usw... die sollen wir lösen ohne irgendwie daran Teilzunehmen !!! Einfach nur ne Hausaufgabe die doppelt zählt, weil die so schwer ist! Mir ist diese Note sehr wichtig und deshalb versuche ich jede Hilfe zu bekommen die ich irgendwo her bekommen kann.

Zwingt dich ja keiner mir zu helfen aber hätte viel geholfen wenn du diese Aufgabe schon fertig hast. Naja kann man nix machen ...

MFG
Night ;-)

[terra-power]

Hier die Lösung. Mein Programm ist zwar in c++, aber das schnell in pascal umzuschreiben ist ja kein Hit. Musst noch die usereingaben machen ... aber etwas arbeiot will ich dir ja auch lassen, ansonsten funktioniert das programm prima. Bei fragen melde dich:

Hier der Quelltext:

/*
--
-- AUFGABE ZUR LÖSUNG DER NÄRRISCHEN WIRTSCHAFT
--
-- BEISPIELLÖSUNG ... GPL Veröffentlichung von Marc Reichenbach 
*/

#include <iostream>

using namespace std;

struct gegenstand {
  int kosten;
  bool besitzen;
  bool temp_besitzen;
};


int main() {
  // Konstanten festlegen
  const int LENGTH = 6;
  const int buget = 1000; 
  
  // Array anlegen für die Gegenstände
  gegenstand g[LENGTH];
  
  // Werte müssen geordnet sein
  // Hier müsste eigentlich der User die Werte angeben
  g[0].kosten = 340;
  g[1].kosten = 670;
  g[2].kosten = 790;
  g[3].kosten = 1320;
  g[4].kosten = 2100;
  g[5].kosten = 5200;

  for (int i =0; i < LENGTH; i++) {
	  g[i].besitzen = false;
	  g[i].temp_besitzen = false;
  }
  
  // Hauptschleife, läuft solange bis alle Gegenstände erworben sind...
  bool alle_erworben = false;
  int monate = 0;
  int geld = 0;
  int temp_geld = 0;
  bool gekauft = false;
  
  while (!alle_erworben) {
    geld = buget;
    monate++;
	cout << "---------------------------------" << endl;
	cout << "Monat:" << monate << endl;
    cout << "\n";
	// Gegenstand "j" kaufen
	for (int j = LENGTH-1; j >= 0; j--) {
		if (g[j].besitzen) continue;
		cout << "Kann ich mir den Gegenstand fuer " << g[j].kosten << " leisten? ..."<<endl;

		temp_geld = geld;
		// Alle billigeren Gegenstände durchlaufen
		for (int k = j; k>= 0; k--) {
		
			// Geld zusammenkratzen durch verkäufe
			if (g[k].besitzen) {
				geld += g[k].kosten;
				g[k].temp_besitzen = false;
			}

			// Erfolgreich, Gegenstand kaufen
			if (geld >= g[j].kosten) {
				cout << "JA -> Gegenstand fuer " << g[j].kosten << " gekauft ... folgene Verkaufe waren notwendig: " << endl;
				geld = geld - g[j].kosten;
			    g[j].besitzen = true;
				g[j].temp_besitzen = true;
			    // Die Verkäufe updaten
				for (int l = 0; l < LENGTH; l++) {
					if (g[l].besitzen != g[l].temp_besitzen) {
					  g[l].besitzen = g[l].temp_besitzen;
					  cout << "^-- Gegenstand fuer " << g[l].kosten << " verkauft ..." << endl;
					}
				}
				// Weitermachen und versuchen nächsten gegenstand zu erwerben.
				cout << "\n\n";
				gekauft = true;
				break;
		    }
			
		}
		
		if (!gekauft) {
		// Nicht gelungen durch Geld zusammenkratzen ... -> Alte Besitztümer wieder herstellen und Geld updaten
				for (int l = 0; l < LENGTH; l++) {
					g[l].temp_besitzen = g[l].besitzen;
				}
			    geld = temp_geld;
				cout << "Nein."<< endl;
				
		}
		gekauft = false;
	}
  
	// check ob alles erworben und aufräumarbeiten
    alle_erworben = true; 
    for (int i =0; i < LENGTH; i++) {
	  if (g[i].besitzen == false) alle_erworben = false;
    }



  } 
  cout << "Alle Gegenstaende gekauft ... " << endl; 
  cin >> gekauft;
  
}

Hier die Ausgabe:

---------------------------------
Monat:1

Kann ich mir den Gegenstand fuer 5200 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 2100 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
JA -> Gegenstand fuer 790 gekauft ... folgene Verkaufe waren notwendig:


Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:2

Kann ich mir den Gegenstand fuer 5200 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 2100 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
JA -> Gegenstand fuer 1320 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 790 verkauft ...


Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
JA -> Gegenstand fuer 340 gekauft ... folgene Verkaufe waren notwendig:


---------------------------------
Monat:3

Kann ich mir den Gegenstand fuer 5200 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 2100 leisten? ...
JA -> Gegenstand fuer 2100 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 1320 verkauft ...


Kann ich mir den Gegenstand fuer 1320 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
---------------------------------
Monat:4

Kann ich mir den Gegenstand fuer 5200 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
JA -> Gegenstand fuer 1320 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 340 verkauft ...


Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:5

Kann ich mir den Gegenstand fuer 5200 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
JA -> Gegenstand fuer 790 gekauft ... folgene Verkaufe waren notwendig:


Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:6

Kann ich mir den Gegenstand fuer 5200 leisten? ...
JA -> Gegenstand fuer 5200 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 790 verkauft ...
^-- Gegenstand fuer 1320 verkauft ...
^-- Gegenstand fuer 2100 verkauft ...


Kann ich mir den Gegenstand fuer 2100 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:7

Kann ich mir den Gegenstand fuer 2100 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
JA -> Gegenstand fuer 790 gekauft ... folgene Verkaufe waren notwendig:


Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:8

Kann ich mir den Gegenstand fuer 2100 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 1320 leisten? ...
JA -> Gegenstand fuer 1320 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 790 verkauft ...


Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
JA -> Gegenstand fuer 340 gekauft ... folgene Verkaufe waren notwendig:


---------------------------------
Monat:9

Kann ich mir den Gegenstand fuer 2100 leisten? ...
JA -> Gegenstand fuer 2100 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 1320 verkauft ...


Kann ich mir den Gegenstand fuer 1320 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
---------------------------------
Monat:10

Kann ich mir den Gegenstand fuer 1320 leisten? ...
JA -> Gegenstand fuer 1320 gekauft ... folgene Verkaufe waren notwendig:
^-- Gegenstand fuer 340 verkauft ...


Kann ich mir den Gegenstand fuer 790 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:11

Kann ich mir den Gegenstand fuer 790 leisten? ...
JA -> Gegenstand fuer 790 gekauft ... folgene Verkaufe waren notwendig:


Kann ich mir den Gegenstand fuer 670 leisten? ...
Nein.
Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:12

Kann ich mir den Gegenstand fuer 670 leisten? ...
JA -> Gegenstand fuer 670 gekauft ... folgene Verkaufe waren notwendig:


Kann ich mir den Gegenstand fuer 340 leisten? ...
Nein.
---------------------------------
Monat:13

Kann ich mir den Gegenstand fuer 340 leisten? ...
JA -> Gegenstand fuer 340 gekauft ... folgene Verkaufe waren notwendig:


Alle Gegenstaende gekauft ...

Die Files hängen auch noch mal dran. Also die Quelltextdatei und die ausführbare exe.

[nightwarrior]

Super Danke Terra-Power

das hilft auf jeden fall mal.. Werde sofort mal versuchen das dann umzusetzen in Delphi.
Falls was unklar ist meld ich mich bei dir ;-)

MFG
Night

[terra-power]

Für Danke gibts nen Button ... :-)

Kannst du das Program nicht in c++ abgeben? Ist doch eigentlich quatsch, das umzusetzen ... Aber nochmal was zum eigentlichen programm, was ich vergessen hatte.

Das Programm verwendet einen Approximationsalgorithmus. Falls dir das nicht bekannt ist ne kurze erklärung: Das Problem ist schwer zu lösen... Also extrem schwer zulösen, deswegen heißt es NP hart bzw. NP vollständig. Anders ausgedrückt heißt das, um die BESTE Lösung zu finden, müsste man alle möglichen kauf und verkaufoperation ausprobieren. Das sind jedoch so viele, das es kein rechner auf der welt schaffen würde, in annehmbarer zeit, das problem für große eingabemengen zu lösen. Wir reden hier von programmlaufzeiten von mehreren hundert jahren. Deswegen sucht das programm eine gute lösung ... eine sehr gute um genau zu sein. Es ist aber eben nicht auszuschlißen, dass es noch eine besser geben kann. Und genau das ist die sogenannte approximation (annäherung). Also nochmal zusammengfasst:

Das programm findet eine sehr gute lösung. (man sieht das daran, das das programm die 13 monate, die vorgegeben waren nicht überscheitet). Es ist aber möglich, dass es noch eine bessere gibt, diese ist aber praktisch nicht zu finden.

noch was abschließendes. Das programm hat ein manko (was man aber vielleicht noch einprogrammieren könnte): Gibt man daten ein, die nicht zu lösen gehen. Meinetwegen ein monatliches buget von 1000 euro
ein gegenstand kostet 100 euro, der andere 2000 euro, so kann man offensichtlich, den für 2000 euro nicht erwerben, da 1000 + 100 < 2000 ist. Bei solchen daten würde das programm endlos lange laufen ... das wäre ja nicht erwünscht ... Also müsste man am anfang abfragen, ob es überhaupt irgendwie möglich ist alle gegenstände zu erwerben. das wär eine zusätliche schleife ganz am anfang, welche prüft ob die summe der ersten n elemente teurer als das n+1. element ist.

[nightwarrior]

Oh sorry bin ja neu hier in diesem Forum habs übersehen ^^

Hab dir sofort ein Dank gegeben, gerne wieder ;-) !

Habs jetzt mal versucht in Delphi umzuschreiben aber hab laufend probleme beim Ausführen der kennt manche Befehle nicht ... mhh warum muss das immer so schwer sein :-(.

wenn du noch weitere Tipps für mich hast ich kann alles gebrauchen :-)

Danke schon mal für alles ist wirklich eine sehr große Hilfe.

MFG Night