מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/יריד תעסוקה 2/שאלה

ליריד התעסוקה של האוניברסיטה הגיעו $\displaystyle m$ סטודנטים, $\displaystyle 1,\ldots m$, ו$\displaystyle n$ חברות, $\displaystyle 1,\ldots n$. נניח שכל סטודנט מוכן לעבוד בחברה אחת או יותר, וכל חברה מוכנה להעסיק סטודנט אחד או יותר, אך כל סטודנט יכול לעבוד בחברה אחת לכל היותר, וכל חברה יכולה להעסיק מספר ידוע של סטודנטים, שהוא לפחות 1.

נתון מערך רצון התעסוקה W, שבו $\displaystyle r$ זוגות. אם הזוג (i, j) מופיע בW, אז המשמעות היא שסטודנט $\displaystyle i$ מוכן לעבוד בחברה $\displaystyle j$, וחברה $\displaystyle j$ מוכנה להעסיק את סטודנט $\displaystyle i$. כמו כן, נתון מערך פוטנציאל ההעסקה P, שבו $\displaystyle n$ מספרים שלמים. P[j] מתאר את מספר המשרות הפנויות בחברה $\displaystyle j$ .

רוצים למצוא את השמת הסטודנטים לחברות כך שמספר רב ככל האפשר של סטודנטים יעבדו. אנא הסבר כיצד לכתוב אלגוריתם יעיל המקבל את המערך $\displaystyle W$, ומוציא מערך גדול ככל האפשר W', כך שיתקיימו התנאים הבאים:

1. אם הזוג (i, j) מופיע בW', אז הוא גם מופיע בW.
2. אם הזוג (i, j) מופיע בW', אז אין זוג אחר בW' שאברו הראשון $\displaystyle i$.
3. מספר הזוגות מהצורה (i, j) בW' בעלי אותו $\displaystyle j$, הוא לכל היותר $\displaystyle P[j]$.