[QUIZ#15] Jellysheep (C++) [2]

[Jellysheep]

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.

#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.

 

[OnlyFoo]

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...

 

[Jellysheep]

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