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.

Code cpp:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247

#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; }

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!