[HaBo]

Mana

Anzeige

Hallo Leute;
also: ich versuche ein Programm zu schreiben, in dem folgendes Problem behandelt wird:
Wir haben Projekttage, und es gibt x Projekte; in jedes Projekt assen aber nur bestimmte anzahlen von Teilnehmern. Jeder Teilnehmer füllt daher einen Zettel aus, mit den drei Lieblingsprojekten.
Wie kann ich jetzt errechnen, was die bestmögliche Aufteilung der Teilnehmer auf die Projekte ist?
Ich dachte bis jetzt daran, dem 1. Wunsch einen Punkt, dem 2. zwei und dem 3. drei Punkte zuzuweisen, und andere Fälle zu verbieten und dann dem Programm zu sagen, es solle mir bitte die beste Kombination sagen (niedrigstmögliche Summe also) - allerding geht das nur, wenn er alle Möglcihkeiten durchgeht - das dauert zu lange.
Daher wollte ich wissen, wie ihr das machen würdet...
(Unser Informatiklehrer meinte, dass ginge mit Matrizen - aber da habe ich keine Möglichkeit gefunden)
Eure Mana

THRALL

Hallo,

1. Welche Programmiersprache verwendet ihr/du ?


Meine Idee:

Man kann davon ausgehen das alle Kurse teilweise belegt werden.
Dann würde ich erstmal versuchen alle teilnehmer nach ihrer ersten wahl auf die kurse zu verteilen. Falls der gewünschte schon voll ist dann die 2. Wahl und wenn die 3. Wahl auch voll ist dann nimmst du nen zufälligen aus der 1. Wahl raus und stekcst den in seine 2. Wahl ...

PS: Bei uns heißt das Sommertage und wir haben nur 2 Wahlmöglichkeiten^^

Mana

uns stehen verschidene Sprachen zur Verfügung (C++, C#, PHP, Java, VB)
das Problem an deiner Lösung ist nur, dass nicht zwangsläufig die niedrigste Gesamtsumme rauskommt, bezeihungsweise, nicht beachtet wird, ob es nicht besser wäre den einen nur den 2. Wunsch zu geben, um einem anderen überhaupt einen Wunsch zu erfüllen - das ist einer der schwersten Punkte, an denen wir nicht vorbeikomen...

~edit~ Der Problemkern kommt ja oft wieder - zum Beispiel bei den Kursplanungen in der Schule dürfen sich ja keine Kurse überschneiden, wo die selben schüler/Lehrer drin sind. - das äre nur eine andere Art des Problems...

THRALL

Kann an denn davon ausgehen, dass alle Kurste stattfinden und Terminmäßig arangiert sind ?

Mana

ja, alle Kurse solen stattfinden;
nur sollen sie halt aufgeteilt werden - und da weiß ich nicht, wie ich an die best-mögliche Lösung komme...

ravenstorm04

ich weiß nicht ob das hier geht, aber ich glaube das müsste mit constraint-programmierung
recht gut lösbar sein(vllt auch anders aber bei meinen praktikum wurde das so gelöst).
ich kann das hier net ganz erklären, da ich das nur 2 wochen gemacht hab.
Allerdings läuft es wesentlich schneller als generate&test bei solchen problemen.
ich gib mal als links :
http://clip.dia.fi.upm.es/~vocal/pub...tes/node6.html
http://en.wikipedia.org/wiki/Constraint_programming
http://en.wikipedia.org/wiki/Constra...ic_programming

außerdem hast du da backtracking zur verfügung und kannst so bessere/andere lösungen "suchen" gehen.

mfg rs04

lightsaver

jaaaaaa, das ist eindeutig was für backtracking, aber vorsicht, wenn man sich dort vertut, können die programme ziemlich lange laufen ;-)

blueflash

Quatsch, das ist eindeutig Simulated Annealing!!!
Oder doch gentische Algorithmen?

Im Ernst, das ist ein nichtlineares Optimierungsproblem und die können schon ganz schön haarig werden.
Wenn du was fertig hast, sag bescheid...

schmidtl_dd

Irgendwie schreit das nach PROLOG

Strahl

ich würde das über punkte machen.

__________________
Kalorienverbrauch