|
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.
Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to the latest Netscape.
More information
The problem instances for the first task have been changed, since the capacity was set too high. If you already used the old ones, you don't need to redo the exercise.
In order to fulfill the attestation conditions, at least 40 points need to be reached for each project and 200 points in total. Task 1 has to be submitted by March 5, 24:00 and task 2 by March 12, 24:00.
Teaching Assistant: Johannes Bader
Preliminary Discussion
Discussion of Task 1
Discussion of Task 2
Task 1
Instance 1 (8 items)
Instance 2 (12 items)
Instance 3 (16 items)
Instance 4 (20 items)
Task 2
All problem parameters are stored in ASCII text files. Each line contains one integer number followed by a newline character. The numbers are sorted in the following order:
<number of items n>
<profit of item 1>
<profit of item 2>
...
<profit of item n>
<weight of item 1>
<weight of item 2>
...
<weight of item n>
<capacity>
For example :
describes a knapsack of capacity 20 with 3 items with profit 125, 321 and 105 respectively and correspondings weights 10,12 and 9.3
125
321
105
10
12
9
20