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