// g++ knapsack_selection.cpp #include #include #include // currentVolume: Das restliche (freie) Volumen im Rucksack // i: Aktueller Gegenstand // Return value: Maximaler Wert mit bzw. ohne den aktuellen Gegenstand int knapsack( const int currentVolume, const int i ); // Maximale Anazahl an Gegenständen const int maxN = 10; // Maximales Volumen des Rucksacks const int maxV = 30; // Anzahl an Byte für unseren Dynamisierungs-Array const int resultLength = ( maxV + 1 ) * sizeof( int ); // Volumen des Rucksacks int V; // Anzahl an Gegenständen int n; // Volumen der einzelnen Gegenstände int v[maxN]; // Werte der einzelnen Gegenstände int w[maxN]; // Gespeicherte Ergebnisse von bisherigen Berechnungen int results[maxN][maxV + 1]; int main() { // Eingabe der Daten scanf( "%d %d", &V, &n ); for( int i = 0; i < n; i++ ) scanf( "%d %d", &( v[i] ), &( w[i] ) ); // Initialisierung der Dynamisierungs-Matrix mit -1 for( int i = 0; i < n; i++ ) memset( results[i], -1, resultLength ); // Berechnung des optimalen Wertes int r = knapsack( V, 0 ); // Belegtes Volumen beim optimalen Ergebnis suchen. // Das optimale Ergebnis befindet sich immer in der ersten Spalte! int currentVolume = -1; for( int i = 0; i <= maxV && currentVolume == -1; i++ ) { if( results[0][i] == r ) currentVolume = i; } // Über alle Gegenstände iterieren (-1, weil mit i+1 gerechnet wird) for( int i = 0; i < n - 1; i++ ) { // Zuerst prüfen ob der aktuelle Gegenstand überhaupt in den Rucksack passt, dann // versuchen den aktuellen Gegenstand aus dem Rucksack zu nehmen. // Stimmt der Wert an der neuen Position? // aktueller Wert im Rucksack - Wert des aktuellen Gegenstands // == Maximum für diesen Gegenstand mit dem neuen Volumen if( currentVolume - v[i] >= 0 && r - w[i] == results[i + 1][currentVolume - v[i]] ) { // Gegenstand war im Rucksack printf( "selecting %d (%d / %d)\n", i + 1, v[i], w[i] ); // Restlichen Wert im Rucksack anpassen r -= w[i]; // Restliches Volumen der Gegenstände im Rucksack anpassen currentVolume -= v[i]; } else { // Gegenstand war nicht im Rucksack printf( "NOT selecting %d (%d / %d)\n", i + 1, v[i], w[i] ); } } // Der letzte Gegenstand muss speziell geprüft werden, da der Index // i + 1 dann nicht mehr vorhanden ist. // Ist jetzt noch etwas im Rucksack, muss es der letzte Gegenstand sein. // r entspricht damit auch dem Wert des letzten Gegenstandes if( r > 0 ) printf( "selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] ); else printf( "NOT selecting %d (%d / %d)\n", n, v[n - 1], w[n - 1] ); return 0; } int knapsack( const int currentVolume, const int i ) { if( i < n ) { if( results[i][currentVolume] != -1 ) return results[i][currentVolume]; return results[i][currentVolume] = std::max( knapsack( currentVolume, i + 1 ), ( currentVolume - v[i] >= 0 ) ? ( w[i] + knapsack( currentVolume - v[i], i + 1 ) ) : 0 ); } return 0; }