W
Hallo,
tja die Ueberschrift ist eigentlich etwas falsch, da mir das Problem, "ich packe meinen Koffer..." durchaus bekannt ist, allerdings habe ich dazu im Sedgewick folgende Loesung gefunden, die unter Rucksackproblem "(dynamisches Programmieren)" gegeben wird, diese ist mir vollkommen unverstaendlich.
Das Problem: Man hat versch. Gegenstaende, die alle eine Laenge und Breite haben, der Rucksack hat jedoch nur ein begrenztes Fassungsvermoegen, nun soll herausgefunden werden wieviele und welche Gegenstaende rein koennen.
So schoen so gut, aber dann wird diese Funktion gegeben, leider eben wieder keine weitere Definition. Ich denke dass es sich dabei allerdings um ein Standardproblem handelt, das der eine oder andere schon mal hatte und daher dieses Bsp in aehnlicher Weise kennt. Der Sedgewick ist ja von der Codierung her teilweise etwas kryptisch und hin und wieder funzen die Bsps auch nicht, was man aber eben auch als Aufgabe sehen kann, allerdings bleibt mir eben hier jeglicher Ansatz schleierhaft.
Evtl kann ja jemand meine Fragen dazu beantworten.
int knap( int M) // M soll wohl der Platz sein ?!
{
int i, space, max, maxi = 0, t;
if( maxKnown[M] != unknown) // Was soll hier unknown sein?
{ // ...und was wird hier eigentlich geprueft ?
return maxKnown[M];
}
for( i = 0, max = 0; i < N; i++)
{
space = M - items[i].laenge;
if( space >= 0)
{
t = knap( space) + items[i].breite;
if( t > max)
{
max = t;
maxi = i;
}
}
}
maxKnown[M] = max;
itemKnown[M] = items[maxi];
return max;
}
// items[] stellt das Array der Gegenstaende die zur Verfuegung
// stehen, dar. Der Typ ist zB eine struct namens item
// Wozu dient hier maxKnown[M] und warum als Array mit Index M???
// Was ist itemKnown[M] mit Index M, was steht denn vorher oder nacher
// in dem Array??
Danke
