מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/תכנון פרוייקטים/שאלה

בבעיית "תכנון הפרוייקטים" יש $\displaystyle k$ פרוייקטים ו$\displaystyle n$ עובדות. צריך להחליט כמה עובדות יש להקצות לכל אחד מהפרוייקטים.

לכל פרוייקט $\displaystyle 1\leq i\leq k$ ומספר עובדות $\displaystyle 1\leq j\leq n$, ‏ $\displaystyle q(i,j)$ הוא מספר המייצג את איכות ביצוע הפרוייקט ה$\displaystyle$i אם ישבצו לו $\displaystyle j$ עובדות. הנח:

1. $\displaystyle q(i,j)$ פונקציה לא שלילית (אין איכות שלילית).
2. $\displaystyle q(i,j)$ מונוטונית לא-יורדת ב$\displaystyle j$ (הוספת עובדות לפרוייקט אינה מורידה מאיכותו).
3. ניתן להקצות 0 עובדות לפרוייקט.
4. כל עובדת מוקצת לפרוייקט אחד בדיוק.

לכל פרוייקט $\displaystyle i$ יש "חשיבות" לא-שלילית $\displaystyle h(i)$. אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את $\displaystyle \max _{i_{1},i2,\ldots ,i_{n}:i_{1}\geq 0,\ldots ,i_{n}\geq 0,i_{1}+\cdots +i_{n}=n}\sum \left[h(i)q(i,j)\right]$.

אנא הצע אלגוריתם יעיל לפתרון הבעיה, כלומר אלגוריתם שימצא את הסכום הנ"ל המקסימלי וכן ידפיס את אופן הקצאת העובדות לכל פרוייקט. הנח שq(i, j) וh(i) הן פונקציות נתונות לך, שעלות קריאה להן היא $\displaystyle O(1)$.