Allgemeines Programmierproblem

M

Mana

0
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
 
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^^
 
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...
 
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...
 
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/public_info/seminar_notes/node6.html
http://en.wikipedia.org/wiki/Constraint_programming
http://en.wikipedia.org/wiki/Constraint_logic_programming

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

mfg rs04
 
jaaaaaa, das ist eindeutig was für backtracking, aber vorsicht, wenn man sich dort vertut, können die programme ziemlich lange laufen ;-)
 
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...
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben