fork download
copy 
  1. // g++ knapsack_greedy.cpp
  2. #include <cstdio>
  3. #include <cstring>
  4.  
  5. // Berechnet den Greedy-Wert aller Gegenstände
  6. void rateItems();
  7. // Sortiert Gegenstände nach Greedy-Wert und Volumen (basiert auf Selectionsort)
  8. void sortItems();
  9.  
  10. // Maximale Anazahl an Gegenständen
  11. const int maxN = 300;
  12. // Maximales Volumen des Rucksacks
  13. const int maxV = 1000;
  14.  
  15. // Volumen des Rucksacks
  16. int V;
  17. // Anzahl an Gegenständen
  18. int n;
  19. // Volumen der einzelnen Gegenstände
  20. int v[maxN];
  21. // Werte der einzelnen Gegenstände
  22. int w[maxN];
  23. // Maximaler Wert des Rucksacks
  24. int maxValue = 0;
  25. // Greedy-Bewertung der einzelnen Gegenstände
  26. float greedyValues[maxN];
  27.  
  28. int main()
  29. {
  30.   // Eingabe der Daten
  31.   scanf( "%d %d", &V, &n );
  32.   for( int i = 0; i < n; i++ )
  33.     scanf( "%d %d", &( v[i] ), &( w[i] ) );
  34.   // Gegenstände bewerten und sortieren
  35.   rateItems();
  36.   sortItems();
  37.   // Die besten (nach Greedy-Bewertung) Gegenstände auswählen, die noch Platz haben
  38.   for( int i = 0; i < n; i++ )
  39.   {
  40.     // Prüfen, ob der Gegenstand noch Platz im Rucksack hat
  41.     if( V - v[i] >= 0 )
  42.     {
  43.       maxValue += w[i];
  44.       V -= v[i];
  45.     }
  46.   }
  47.   printf( "%d\n", maxValue );
  48.   return 0;
  49. }
  50.  
  51.  
  52. void rateItems()
  53. {
  54.   for( int i = 0; i < n; i++ )
  55.     greedyValues[i] = (float) w[i] / (float) v[i];
  56. }
  57.  
  58.  
  59. void sortItems()
  60. {
  61.   int max;
  62.   int tmp;
  63.   for( int i = 0; i < n; i++ )
  64.   {
  65.     max = i;
  66.     for( int j = i + 1; j < n; j++ )
  67.     {
  68.       if( greedyValues[j] > greedyValues[max] )
  69.         max = j;
  70.       else if( greedyValues[j] == greedyValues[max] && v[j] > v[max] )
  71.         max = j;
  72.     }
  73.     if( max != i )
  74.     {
  75.       tmp = v[max];
  76.       v[max] = v[i];
  77.       v[i] = tmp;
  78.       tmp = w[max];
  79.       w[max] = w[i];
  80.       w[i] = tmp;
  81.     }
  82.   }
  83. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cs(3,0): error CS1024: Wrong preprocessor directive
prog.cs(4,0): error CS1024: Wrong preprocessor directive
prog.cs(6,0): error CS1525: Unexpected symbol `void'
Compilation failed: 3 error(s), 0 warnings
stdout
copy 
Standard output is empty
https://ideone.com/DMUdUo
language:
C# (gmcs 5.20.1)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!