| [VIROR] | [ULI] | [Institut für Informatik] | [Fakultät für Angewandte Wissenschaften] | [Universität Freiburg] |
| [Home] [Ebene höher] [Seitenende] [Suchen] [Kontakt] | [
|< ] [
< ] [
> ] [
>| ] Kummerkasten - Forum für Fragen und Probleme (SS 98): 6 von 14 |
Re: Betrifft InfoII Blatt T3 Aufgabe 1
Sehr geehrte Info-II-Studenten, ich finde es gut, dass Sie sich mit Fragen an uns wenden, denn nur so koennen wir erkennen, wenn es irgendwo Probleme gibt. Schicken Sie in Zukunft Fragen mit allgemeinem Interesse bitte an kummerkasten@informatik.uni-freiburg.de damit auch andere Studenten die Moeglichkeit zur Diskussion haben und von den Antworten profitieren koennen. Ich habe mir die Aufgabenstellung zu A9 auf T3 nochmal angesehen. Die Formulierung der Aufgabe stammt ja von Dr. Juergen Eckerle, der Ihre Frage ebenfalls beantworten koennte. Da Herr Eckerle aber diese Woche Urlaub hat, will ich die Beantwortung hier gerne uebernehmen. Mir erscheint die Aufgabe klar formuliert. Es heisst: Gesucht: (Eine Liste) x_1, ..., x_n, wobei jedes x_i aus {0,1} ist, so dass die Summe der Produkte (x_i * a_i) fuer i von 1 bis n gleich b wird.(Der i-te Gegenstand mit Gewicht a_i wird also genau einmal (x_i=1) oder gar nicht (x_i=0) eingepackt, und die Summe der Gewichte der eingepackten Gegenstaende soll gleich b sein.) Die x_i sind natuerlich nicht immer eindeutig zu bestimmen, es kann mehrere Loesungen geben. Aber eine Loesung reicht (da nicht nach saemtlichen Loesungen gefragt ist). Zudem: Wollte man saemtliche Loesungen ausgeben, koennte das ueberaus aufwendig werden (etwa: n=100, a_i=1 fuer alle i, b=50), und der zweite Aufgabenteil waere sinnlos. Es kann auch sein, dass es keine Loesung gibt. Ihre Frage bezieht sich vielleicht auf diesen Fall. Hier reicht sicher zunaechst eine Ausgabe der Form: Es existiert keine Loesung in diesem Fall. Aber eine andere Ausgabe liefert doch noch mehr Informationen: So koennte man solche x_i ausgeben, so dass die oben definierte Summe maximal wird unter allen Summen <= b. (Dies zeigt, wie die gestellte Aufgabe als Optimierungsaufgabe verstanden werden kann. Ein Schritt zur Loesung liefert die Fallunterscheidung: Wird der i-te Gegenstand eingepackt oder nicht?) Ein Beispiel: n=11 Ich hoffe, dass Ihre Fragen damit hinreichend praezise beantwortet wurden, und wuensche viel Spass bei der Loesung! Alois Heinz -- Drei Studenten fragten an: Sehr geehrter Herr Heinz, Nach mehrfachen Auseinandersetzen mit dem Problem der Aufgabe 1 auf Blatt T3 sind wir zu der Meinung gekommen, dass die Aufgabe 1 nicht eindeutig ist. Sollen das Programm alle Moeglichkeiten finden? Gibt es ein Optimum, fuer die Packung des Rucksacks, das es zu finden gilt? Welche Kriterien sollen fuer Loesung gelten? |
| [Seitenanfang] |