Hier ist meine zweite Lösung für das Quiz in C++, sie arbeitet wie in meiner ersten Lösung, nur ist der Algorithmus durch die dynamische Programmierung (siehe Rucksackproblem) ersetzt und dadurch ist das Programm deutlich schneller geworden (es braucht aber auch einiges an Arbeitsspeicher).
An dieser Stelle ein großes Dankeschön an OnlyFoo, ohne den ich die dynamische Programmierung nicht vervollständigen hätte können.

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

#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_kcals; unsigned int max_weight; unsigned int max_kcals_weight; unsigned int count_eggs; stringstream tmp; unsigned int time_read;   struct position{     int x, y; };   struct matrix_element{     int value;     position pos; };   void check();   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()<<"\n";     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<<"\nMaximales Gewicht: "<<max_weight<<" g\n\n";     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";     time_read = clock()-time;     check();     cin.get();     return 0; }   void check(){     unsigned long time = clock();     unsigned int B = max_weight;     unsigned int n = count_eggs;     vector< vector<matrix_element> > R;     R.resize(n+1);     unsigned int i, j, value1, value2, y;     for(i = 0; i<=n+1; i++){         R.push_back(vector<matrix_element>());         R[i].resize(B);         for(j = 0; j<=B; j++){             R[i].push_back(matrix_element());             R[i][j].value = 0;             R[i][j].pos.x = 0;             R[i][j].pos.y = 0;         }     }     cout<<"Array erstellt! Bitte warten...\n\n";     for(i = n; i>=1; i--){         for(j = 1; j<=B; j++){             if(weights[i-1] <= j){                 y = j-weights[i-1];                 value1 = kcals[i-1]+R[i+1][y].value;                 value2 = R[i+1][j].value;                 if(value1>value2){                     R[i][j].value = value1;                     R[i][j].pos.x = i+1;                     R[i][j].pos.y = y;                 }else{                     R[i][j].value = value2;                     R[i][j].pos = R[i+1][j].pos;                 }             }else{                 R[i][j].value = R[i+1][j].value;                 R[i][j].pos = R[i+1][j].pos;             }         }     }     unsigned long time_diff = clock()-time;     cout<<"Fertig! Benötigte Zeit: "<<time_diff<<" ms (+ "<<time_read<<" ms Einlesezeit)\n\n";     max_kcals = R[1][B].value;         std::vector<int> path;     position p = R[1][B].pos;     while(p.x) {         path.push_back(p.x-2);         p = R[p.x][p.y].pos;     }     cout<<"Beste Kombination: \n";     for(i = 0; i<path.size(); i++){         cout<<names[path[i]]<<"; ";         max_kcals_weight += weights[path[i]];     }     cout<<"\nBrennwert: "<<max_kcals<<" kcal\n";     cout<<"Masse: "<<max_kcals_weight<<" g\n"; }

Ausgabe bei einer Datei mit 100.000 zufälligen Eiern (liegt im Anhang):

C:\Dokumente und Einstellungen\Admin\Desktop\100k.txt

Maximales Gewicht: 500 g

Anzahl der Eier: 100000

Array erstellt! Bitte warten...

Fertig! Benötigte Zeit: 7281 ms (+ 1610 ms Einlesezeit)

Beste Kombination:
ei-2383; ei-23359; ei-40669; ei-47555; ei-62142; ei-62736; ei-65451; ei-66390; ei-77632; ei-79046;
Brennwert: 9983 kcal
Masse: 500 g

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

PS: Wenn das Programm abstürtzt, liegt das wahrscheinlich an zu wenig Arbeitsspeicher, dann muss entweder die Anzahl der Eier oder die maximale Masse verringert werden.

Tipp: std::vector bietet einen Konstructor std::vector<T>( size_t n, const T& t = T() ) der die neue Instanz mit n-Kopien von t initialisiert...

Danke für den Tipp! Daran hab ich nicht gedacht...
Und danke nochmal für deine Unterstützung bei der dynamischen Programmierung!