// g++ knapsack_greedy.cpp
#include <cstdio>
#include <cstring>
// Berechnet den Greedy-Wert aller Gegenstände
void rateItems();
// Sortiert Gegenstände nach Greedy-Wert und Volumen (basiert auf Selectionsort)
void sortItems();
// Maximale Anazahl an Gegenständen
const int maxN = 300;
// Maximales Volumen des Rucksacks
const int maxV = 1000;
// 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];
// Maximaler Wert des Rucksacks
int maxValue = 0;
// Greedy-Bewertung der einzelnen Gegenstände
float greedyValues[maxN];
int main()
{
// Eingabe der Daten
scanf( "%d %d", &V
, &n
); for( int i = 0; i < n; i++ )
scanf( "%d %d", &( v
[i
] ), &( w
[i
] ) ); // Gegenstände bewerten und sortieren
rateItems();
sortItems();
// Die besten (nach Greedy-Bewertung) Gegenstände auswählen, die noch Platz haben
for( int i = 0; i < n; i++ )
{
// Prüfen, ob der Gegenstand noch Platz im Rucksack hat
if( V - v[i] >= 0 )
{
maxValue += w[i];
V -= v[i];
}
}
return 0;
}
void rateItems()
{
for( int i = 0; i < n; i++ )
greedyValues[i] = (float) w[i] / (float) v[i];
}
void sortItems()
{
int max;
int tmp;
for( int i = 0; i < n; i++ )
{
max = i;
for( int j = i + 1; j < n; j++ )
{
if( greedyValues[j] > greedyValues[max] )
max = j;
else if( greedyValues[j] == greedyValues[max] && v[j] > v[max] )
max = j;
}
if( max != i )
{
tmp = v[max];
v[max] = v[i];
v[i] = tmp;
tmp = w[max];
w[max] = w[i];
w[i] = tmp;
}
}
}
Ly8gZysrIGtuYXBzYWNrX2dyZWVkeS5jcHAKI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdHJpbmc+CgovLyBCZXJlY2huZXQgZGVuIEdyZWVkeS1XZXJ0IGFsbGVyIEdlZ2Vuc3TDpG5kZQp2b2lkIHJhdGVJdGVtcygpOwovLyBTb3J0aWVydCBHZWdlbnN0w6RuZGUgbmFjaCBHcmVlZHktV2VydCB1bmQgVm9sdW1lbiAoYmFzaWVydCBhdWYgU2VsZWN0aW9uc29ydCkKdm9pZCBzb3J0SXRlbXMoKTsKCi8vIE1heGltYWxlIEFuYXphaGwgYW4gR2VnZW5zdMOkbmRlbgpjb25zdCBpbnQgbWF4TiA9IDMwMDsKLy8gTWF4aW1hbGVzIFZvbHVtZW4gZGVzIFJ1Y2tzYWNrcwpjb25zdCBpbnQgbWF4ViA9IDEwMDA7CiAKLy8gVm9sdW1lbiBkZXMgUnVja3NhY2tzCmludCBWOwovLyBBbnphaGwgYW4gR2VnZW5zdMOkbmRlbgppbnQgbjsKLy8gVm9sdW1lbiBkZXIgZWluemVsbmVuIEdlZ2Vuc3TDpG5kZQppbnQgdlttYXhOXTsKLy8gV2VydGUgZGVyIGVpbnplbG5lbiBHZWdlbnN0w6RuZGUKaW50IHdbbWF4Tl07Ci8vIE1heGltYWxlciBXZXJ0IGRlcyBSdWNrc2Fja3MKaW50IG1heFZhbHVlID0gMDsKLy8gR3JlZWR5LUJld2VydHVuZyBkZXIgZWluemVsbmVuIEdlZ2Vuc3TDpG5kZQpmbG9hdCBncmVlZHlWYWx1ZXNbbWF4Tl07CiAKaW50IG1haW4oKQp7CiAgLy8gRWluZ2FiZSBkZXIgRGF0ZW4KICBzY2FuZiggIiVkICVkIiwgJlYsICZuICk7CiAgZm9yKCBpbnQgaSA9IDA7IGkgPCBuOyBpKysgKQogICAgc2NhbmYoICIlZCAlZCIsICYoIHZbaV0gKSwgJiggd1tpXSApICk7CiAgLy8gR2VnZW5zdMOkbmRlIGJld2VydGVuIHVuZCBzb3J0aWVyZW4KICByYXRlSXRlbXMoKTsKICBzb3J0SXRlbXMoKTsKICAvLyBEaWUgYmVzdGVuIChuYWNoIEdyZWVkeS1CZXdlcnR1bmcpIEdlZ2Vuc3TDpG5kZSBhdXN3w6RobGVuLCBkaWUgbm9jaCBQbGF0eiBoYWJlbgogIGZvciggaW50IGkgPSAwOyBpIDwgbjsgaSsrICkKICB7CiAgICAvLyBQcsO8ZmVuLCBvYiBkZXIgR2VnZW5zdGFuZCBub2NoIFBsYXR6IGltIFJ1Y2tzYWNrIGhhdAogICAgaWYoIFYgLSB2W2ldID49IDAgKQogICAgewogICAgICBtYXhWYWx1ZSArPSB3W2ldOwogICAgICBWIC09IHZbaV07CiAgICB9CiAgfQogIHByaW50ZiggIiVkXG4iLCBtYXhWYWx1ZSApOwogIHJldHVybiAwOwp9CgoKdm9pZCByYXRlSXRlbXMoKQp7CiAgZm9yKCBpbnQgaSA9IDA7IGkgPCBuOyBpKysgKQogICAgZ3JlZWR5VmFsdWVzW2ldID0gKGZsb2F0KSB3W2ldIC8gKGZsb2F0KSB2W2ldOwp9CgoKdm9pZCBzb3J0SXRlbXMoKQp7CiAgaW50IG1heDsKICBpbnQgdG1wOwogIGZvciggaW50IGkgPSAwOyBpIDwgbjsgaSsrICkKICB7CiAgICBtYXggPSBpOwogICAgZm9yKCBpbnQgaiA9IGkgKyAxOyBqIDwgbjsgaisrICkKICAgIHsKICAgICAgaWYoIGdyZWVkeVZhbHVlc1tqXSA+IGdyZWVkeVZhbHVlc1ttYXhdICkKICAgICAgICBtYXggPSBqOwogICAgICBlbHNlIGlmKCBncmVlZHlWYWx1ZXNbal0gPT0gZ3JlZWR5VmFsdWVzW21heF0gJiYgdltqXSA+IHZbbWF4XSApCiAgICAgICAgbWF4ID0gajsKICAgIH0KICAgIGlmKCBtYXggIT0gaSApCiAgICB7CiAgICAgIHRtcCA9IHZbbWF4XTsKICAgICAgdlttYXhdID0gdltpXTsKICAgICAgdltpXSA9IHRtcDsKICAgICAgdG1wID0gd1ttYXhdOwogICAgICB3W21heF0gPSB3W2ldOwogICAgICB3W2ldID0gdG1wOwogICAgfQogIH0KfQ==
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