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

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

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

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

לכל פרוייקט $i$ יש "חשיבות" לא-שלילית $h(i)$. אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את $\underset{i_1,i2,\dots ,i_n:i_1\ge 0,\dots ,i_n\ge 0,i_1+\cdots +i_n=n}{\max }\sum [h(i)q(i,j)]$.

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