Jellysheep
Erfahrenes Mitglied
Hier ist meine Lösung des Osterquiz in C++:
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:
Im Anhang liegt das Programm und eine Datei zum Testen.
Viel Spaß damit!
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_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:
Im Anhang liegt das Programm und eine Datei zum Testen.
Viel Spaß damit!
Zuletzt bearbeitet von einem Moderator:
