Hier ist meine Lösung des Osterquiz in C++:

Code cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157

#define STRING_SIZE 200   #include <sstream> #include <iostream> #include <fstream> #include <Windows.h> #include <string.h> #include <vector> #include <time.h>   using namespace std;   vector<string> names; vector<int> weights; vector<int> kcals; unsigned int max_weight; unsigned int count_eggs; unsigned int max_kcals = 0; string max_kcals_kombi; unsigned int max_kcals_weight; unsigned int akt_weight; unsigned int akt_kcals; unsigned int count = 0; unsigned int count2 = 0; unsigned int min_weight; stringstream tmp; int max_kcals_pro_g = 0; vector<int> kombination; const bool check1 = false; const bool check2 = true; unsigned int max_depth; unsigned int time_read;   void check_combi(int *elements, int depth){     count++;     if(count >= 1000000){         count2++;         count = 0;     }     for(unsigned int i = (depth==0?-1:elements[depth-1])+1; i<count_eggs; i++){         akt_weight = weights[i];         for(int j = 0; j<depth; j++){             akt_weight += weights[elements[j]];         }         if(akt_weight <= max_weight){             akt_kcals = kcals[i];             for(int j = 0; j<depth; j++){                 akt_kcals += kcals[elements[j]];             }             if(akt_kcals > max_kcals){                 max_kcals = akt_kcals;                 max_kcals_weight = akt_weight;                 kombination.clear();                 kombination.push_back(i);                 for(int j = 0; j<depth; j++){                     kombination.push_back(elements[j]);                 }             }         }         if(depth<count_eggs-1 && ((akt_weight+min_weight) <= max_weight)                             && (akt_kcals+((max_weight-akt_weight)*max_kcals_pro_g))>max_kcals             ){             elements[depth] = i;             check_combi(elements, depth+1);         }     } }   int main(int argc, char** argv) {     string filename;     if(argc!=2){         OPENFILENAME ofn;         char szFile[260];         HWND hwnd = NULL;         ZeroMemory(&ofn, sizeof(ofn));         ofn.lStructSize = sizeof(ofn);         ofn.hwndOwner = hwnd;         ofn.lpstrFile = szFile;         ofn.lpstrFile[0] = '\0';         ofn.nMaxFile = sizeof(szFile);         ofn.lpstrFilter = "All\0*.*\0Text\0*.TXT\0";         ofn.nFilterIndex = 1;         ofn.lpstrFileTitle = NULL;         ofn.nMaxFileTitle = 0;         ofn.lpstrInitialDir = NULL;         ofn.Flags = OFN_PATHMUSTEXIST | OFN_FILEMUSTEXIST;         if (GetOpenFileName(&ofn)==TRUE){             filename = string(ofn.lpstrFile);         }else{             exit(0);         }     }else{         filename = string(argv[1]);     }     long time = clock();     cout<<filename.c_str()<<endl;     string line, line2;     fstream f;     f.open(filename.c_str(), ios::in);     char* c_line = new char[STRING_SIZE];     char* c_line2 = new char[STRING_SIZE];     f.getline(c_line, STRING_SIZE);     line = string(c_line);     stringstream strstr(c_line);     strstr >> max_weight;     cout<<endl<<"Maximales Gewicht: "<<max_weight<<" g"<<endl<<endl;     unsigned int i = 0, x;     do{         f.getline(c_line, STRING_SIZE);         line = string(c_line);         f.getline(c_line2, STRING_SIZE);         line2 = string(c_line2);         if(line2!="" && line!=""){             i++;             names.push_back(line);             stringstream(line2.substr(0, line2.find_first_of(" "))) >> x;             weights.push_back(x);             stringstream(line2.substr(line2.find_first_of(" "))) >> x;             kcals.push_back(x);         }     }while(line!="");     count_eggs = i;     f.close();     cout<<"Anzahl der Eier: "<<count_eggs<<"\n\n";     min_weight = max_weight;     unsigned int tmp_int;     for(i = 0; i<count_eggs; i++){         if(weights[i]<min_weight){             min_weight = weights[i];         }         tmp_int = kcals[i]/weights[i]+1;         if(tmp_int > max_kcals_pro_g){             max_kcals_pro_g = tmp_int;         }     }     time_read = clock()-time;     time = clock();     cout<<"Bitte warten...\n"<<endl;     int* elements = new int[count_eggs];     check_combi(elements, 0);     long time_diff = clock()-time;     cout<<endl<<"Beste Kombination: "<<endl;     for(unsigned int i = 0; i<kombination.size(); i++){         cout<<names[kombination[i]]<<"; ";     }     cout<<endl<<"Gewicht: "<<max_kcals_weight<<" g"<<endl;     cout<<"Brennwert: "<<max_kcals<<" kcal"<<endl<<endl;     cout<<"Benötigte Zeit: "<<time_diff<<" ms + "<<time_read<<" ms Einlesezeit ";     if(count2>0){         cout<<"("<<count2<<"*1.000.000 + "<<count<<" rekursive Durchläufe)"<<endl<<endl;     }else{         cout<<"("<<count<<" rekursive Durchläufe)"<<endl;     }     cin.get();     return 0; }

Aufzurufen ist das Programm entweder ohne Parameter, dann öffnet sich ein "Datei öffnen..."-Fenster, um die Datei der Eier auszuwählen. Man aber kann auch als Parameter den Pfad zur Datei eingeben.

Das Programm sucht rekursiv alle sinnvollen Kombinationen der Eier durch und schaut nach den größten Kcal-Werten.
Es arbeitet so, dass es alle Eier nacheinander nimmt, an jedes wieder je eines von allen dranhängt usw. Dabei entscheidet es nach jeder Kombination, ob die nächste sinnvoll sein wird, um Rechenzeit zu sparen:
1. Wenn die Summe aus der Masse der aktuellen Kombination und der kleinsten Masse der Eier schon über der Höchstmasse liegt, oder
2. Wenn das Ei mit der größten kcal/g-Eigenschaft das Nest auffüllen würde und diese Kombination immer noch nicht über dem aktuellen maximalen Brennwert liegt,
wird der aktuelle Zweig der Kombinationen abgebrochen.
Dadurch verringert sich der Aufruf der rekursiven Funktion von ca. 3,232 * 10^492 auf 804 Aufrufe.

Bei Eiermengen von 1 bis ca. 500 Eier arbeitet das Programm recht flott, bei größeren Mengen nimmt jedoch leider die Anzahl der Kombinationen und so auch die Rechenzeit exponentiell zu.

Die Ausgabe bei der Datei mit 250 Leckereien:

C:\Dokumente und Einstellungen\Admin\Desktop\250leckereien.txt

Maximales Gewicht: 500 g

Anzahl der Eier: 250

Bitte warten...


Beste Kombination:
Waffel-Keks-Buttereier; Marzipan-Sahne-Butter-Schlemmerhase; Keks-Trüffelhase; Keks-Platineier;
Gewicht: 498 g
Brennwert: 3442 kcal

Benötigte Zeit: 0 ms + 0 ms Einlesezeit (806 rekursive Durchläufe)

Im Anhang liegt das Programm und eine Datei zum Testen.
Viel Spaß damit!

Hallo Jellysheep,

mir ist beim schnellen Überfliegen nur aufgefallen, dass deine Zeitmessung nicht sehr portabel ist. clock gibt im Allgemeinen keine Zeit in Millisekunden zurück, sondern eine Anzahl von „clock ticks“. Um auf Sekunden zu kommen, muss man den Wert mit CLOCKS_PER_SEC multiplizieren. Der Rückgabewert muss auch nicht immer ein long sein. Auf der sicheren Seite ist man, wenn man clock_t verwendet.

Diese 2. Optimierung die du ansprichst – bist du dir sicher, dass die immer korrekt ist? Ich hab es glaub ich noch nicht ganz verstanden. Kannst du vielleicht kurz erklären, was da die Idee dahinter ist?

Grüße,
Matthias

Zitat von Matthias Reitinger

Hallo Jellysheep,

mir ist beim schnellen Überfliegen nur aufgefallen, dass deine Zeitmessung nicht sehr portabel ist. clock gibt im Allgemeinen keine Zeit in Millisekunden zurück, sondern eine Anzahl von „clock ticks“. Um auf Sekunden zu kommen, muss man den Wert mit CLOCKS_PER_SEC multiplizieren. Der Rückgabewert muss auch nicht immer ein long sein. Auf der sicheren Seite ist man, wenn man clock_t verwendet.

Diese 2. Optimierung die du ansprichst – bist du dir sicher, dass die immer korrekt ist? Ich hab es glaub ich noch nicht ganz verstanden. Kannst du vielleicht kurz erklären, was da die Idee dahinter ist?

Grüße,
Matthias

Danke für den Hinweis für die clock-Funktion. (Bei mir ist CLOCKS_PER_SECOND sogar 1000, also stimmen die Ausgaben auf meinem PC sogar. )

Zur 2. Optimierung:
Ich habe mir gedacht, dass der aktuelle Zweig der Kombinationen so sein sollte, dass irgendeine Kombination daraus größer als max_kcals ist. Die maximal mögliche Kombination aus der Reihe würde man (wenn es an diesem Zeitpunkt erlaubt wäre, mehrmals das gleiche Ei zu verwenden) bekommen, wenn man zur jetzigen Kombination so oft das "wertvollste" Ei hinzufügt, bis das Nest voll ist (im Programm kann es sogar Bruchteile des Eies geben, das rechnet sich um ca 50 ms schneller). Wenn diese wertvollste Kombination des Zweiges immer noch kleiner als max_kcals ist, kann keine andere Kombination des Zweiges Sinn machen. Daher wird hier abgebrochen.