Jellysheep
Erfahrenes Mitglied
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.
Ausgabe bei einer Datei mit 100.000 zufälligen Eiern (liegt im Anhang):
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.
An dieser Stelle ein großes Dankeschön an OnlyFoo, ohne den ich die dynamische Programmierung nicht vervollständigen hätte können.
C++:
#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):
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.
Zuletzt bearbeitet von einem Moderator:
