[Quiz#15] OnlyFoo (C++)

OnlyFoo

Erfahrenes Mitglied
Vllt können mögliche C++-Profis mal ein wenig was zum Stil sagen... Ich muss für meine Bachelorarbeit eine Aufgabe in C++ implementieren und da würd ich dann gern möglichst sauberes C++ schreiben...

Ich hab versucht den Algorithmus so abstrakt wie möglich zu halten und komplett unabhängig von der eigentlichen Datenstruktur zu implementieren.

C++:
#include <cstdlib>
#include <ctime>
#include <sys/time.h>

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

#include <limits>


namespace std {
    /* The following code example is taken from the book
     * "The C++ Standard Library - A Tutorial and Reference"
     * by Nicolai M. Josuttis, Addison-Wesley, 1999
     *
     * (C) Copyright Nicolai M. Josuttis 1999.
     * Permission to copy, use, modify, sell and distribute this software
     * is granted provided this copyright notice appears in all copies.
     * This software is provided "as is" without express or implied
     * warranty, and with no claim as to its suitability for any purpose.
     */
    template<class charT, class traits>
    inline
    std::basic_istream<charT,traits>&
    eol (std::basic_istream<charT,traits>& strm)
    {
        // skip until end-of-line
        strm.ignore(std::numeric_limits<int>::max(),strm.widen('\n'));

        // return stream for concatenation
        return strm;
    }
    
    inline
    std::string trim( std::string const& str, char const* what = "\r\n\t " ) {
        const std::string::size_type first = str.find_first_not_of( what );
        return ( first == std::string::npos )
            ? std::string()
            : str.substr( first, str.find_last_not_of(what) - first + 1 );
    }
}

class candy {
    private:
        std::string m_name;
        int m_weight;
        int m_value;
    
    public:
        candy( const std::string &name, int weight, int value );
        
        const std::string& name() const;
        int weight() const;
        int value() const;
};

candy::candy( const std::string &name, int weight, int value )
    : m_name(name), m_weight(weight), m_value(value) {
}

const std::string& candy::name() const {
    return m_name;
}

int candy::weight() const {
    return m_weight;
}

int candy::value() const {
    return m_value;
}

void read_candies( std::vector<candy> &candies ) {
    std::string name;
    std::getline( std::cin, name );
    
    while( name != "" ) {
        int weight, value;
        std::cin >> weight >> value >> std::eol;
        
        candy candy( std::trim(name), weight, value );
        candies.push_back( candy );
        
        std::getline( std::cin, name );
    }
}

time_t mtime() {
    timeval tv;
    gettimeofday( &tv, NULL );
    return static_cast<time_t>( tv.tv_sec*1000 + tv.tv_usec / 1000 );
}

/**
    der Default-Weight-Accessor gibt für eine Vielzahl von Objekt ein Gewicht
    mithilfe der objekt.weight() Methode zurück.
*/
template<class T>
struct default_weight_accessor {
    const std::vector<T>& objects;
    default_weight_accessor( const std::vector<T>& objects )
        : objects( objects ) {}
    
    inline
    int operator()( int idx ) const {
        return objects[idx].weight();
    }
};


/**
    der Default-Value-Accessor gibt für eine Vielzahl von Objekt ein Nutzen
    mithilfe der objekt.value() Methode zurück.
*/
template<class T>
struct default_value_accessor {
    const std::vector<T>& objects;
    default_value_accessor( const std::vector<T>& objects )
        : objects( objects ) {}
    
    inline
    int operator()( int idx ) const {
        return objects[idx].value();
    }
};


/**
    typdefs für einfache, zweidimensionale auf std::vector
    basierende Arrays.
*/
template<class T>
struct matrix {
    typedef std::vector< std::vector<T> > type;
    typedef std::vector<T> row;
};

/**
    Hilfsklasse für die knapsack-Methode
*/
struct knapsack_info {
    int w, x, y;
    knapsack_info() : w(0), x(0), y(0) {}
    inline void set( int w, int x, int y ) {
        this->w = w; this->x = x; this->y = y; }
};


/**
    Generalisierte Methode für das Rucksackproblem.
    Erwartet neben der Anzahl an Objekten n
    und dem maximalen Gewicht threshold 
    zwei Gewichtungsfunktoren value und weight, welche für
    das i-te Objekt seinen Nutzen bzw Gewicht zurückgeben.
    
    Die Rückgabe der Methode besteht aus einer Liste von Elementen,
    die in die Auswahl aufgenommen werden sollen
*/
template<class WeightAccessorType, class ValueAccessorType>
std::vector<int> knapsack(
        const ValueAccessorType& value,
        const WeightAccessorType& weight,
        int n, int threshold ) {
    
    // Matrix mit allen wichtigen Werten erzeugen
    matrix<knapsack_info>::type m( n + 1, matrix<knapsack_info>::row( threshold + 1 ) );
    matrix<knapsack_info>::row::const_iterator itn = m[n].begin();
    
    // Durch die Objekte iterieren
    for( int i = n - 1; i >= 0; --i ) {
        matrix<knapsack_info>::row::iterator begin = m[i].begin(),
            end = m[i].end(),
            it = begin;
        
        // Gewichte probieren
        for( int j = 0; it != end; ++it, ++itn, ++j ) {
            const int w = weight(i);
            
            if( w <= j ) {
                const int c1 = value(i) + (itn - w)->w;
                
                if( c1 > itn->w ) {
                    it->set(c1, i + 1, j - w);
                } else {
                    *it = *itn;
                }
            } else {
                *it = *itn;
            }
        }
        
        // itn für den nächsten Durchlauf auf
        // unser aktuelles Objekt setzen
        itn = begin;
    }
    
    // Pfad vom besten Ergebnis aus zurück verfolgen
    std::vector<int> path;
    knapsack_info i = m[0][threshold];
    while( i.x ) {
        path.push_back( i.x-1 );
        i = m[i.x][i.y];
    }
    
    // Und den Pfad zurück geben!
    return path;
}

int main( int argc, const char *argv[] ) {
    int threshold = 0;
    std::cin >> threshold >> std::eol;
    
    time_t start_read_candies = mtime();
    std::vector<candy> candies;
    read_candies( candies );
    
    time_t start_knapsack = mtime();
    std::vector<int> result = knapsack(
        default_value_accessor<candy>( candies ),
        default_weight_accessor<candy>( candies ),
        candies.size(), threshold );
    
    time_t end = mtime();
    
    int weight = 0, value = 0;
    
    std::cout << "Optimale Auswahl:";
    for( uint i = 0; i < result.size(); i++ ) {
        const candy& candy = candies[ result[i] ];
        
        std::cout << (i ? ", " : " ") << candy.name();
        weight += candy.weight();
        value += candy.value();
    }
    
    std::cout << std::endl;
    
    std::cout << "Masse: " << weight << " g" << std::endl;
    std::cout << "Nährwert: " << value << " kcal" << std::endl;
    std::cout << "Rechenzeit" << std::endl;
    std::cout << "  einlesen:  " << std::setw(5) << std::right << start_knapsack - start_read_candies << " ms" << std::endl;
    std::cout << "  auswählen: " << std::setw(5) << std::right << end - start_knapsack << " ms" << std::endl;
    std::cout << "  gesamt:    " << std::setw(5) << std::right << end - start_read_candies << " ms" << std::endl;
    return 0;
}
 
Zuletzt bearbeitet:

Jellysheep

Erfahrenes Mitglied
Ich kenn mich zwar mit C++ nicht sooo toll aus, aber ich finde den Code gut. Ich würde auf jeden Fall die Klassen in separierten Headern definieren und in separierten C++ -Dateien deklarieren. Evtl. würde ich matrix und default_weight_accessor etc. als Klasse schreiben.
Wo hast du denn die Daten eingelesen? Ich finde das nicht im Code. :-(
[EDIT]
Achso, du machst das über eine Eingabe, und bei der Ausführung gibst du eine Datei an.
Geschickt gelöst! ;)