נתון מערך A באורך N (אין חשיבות לתוכן A). נאמר כי P={[1,i1],[i1+1,i2],…,[ik−1+1,N]} היא חלוקה k-רציפה של מיקומי המערך A, כלומר היא מחלקת את המערך ל-k תתי מערכים (רציפים).
דוגמה: עבור מערך A באורך 14 ו- k=4, חלוקה 4-רציפה אפשרית של המערך A היא:
P={[1,3],[4,8],[9,10],[11,14]}
נניח כי לכל זוג 1≤i≤j≤n נתונה פונקציית עלות כללית C(i,j) המחזירה את העלות של תת המערך מהאינדקס i עד האינדקס j (כולל), קרי [i,j].
נגדיר את מחיר החלוקה P:
cost(P)=C(1,i1)+C(ik−1,N)+ℓ=1∑k−1C(iℓ+1,iℓ+1)
כלומר, מחיר החלוקה הוא סכום העלויות של חלקי החלוקה ה-k רציפה.
להלן הגדרת בעיית החלוקה ה-k-רציפה מינימלית:
קלט: מערך A באורך N, מספר טבעי k, המייצג את מספר תת המערכים הרציפים, ופונקציית עלות כללית C(i,j), המחזירה את עלות החלק [i,j].
פלט: חלוקה k-רציפה P={[1,i1],[i1+1,i2],…,[ik−1+1,N]} של המערך A (ל-k תת מערכים רציפים), שעבורה מחיר החלוקה cost(P) הוא מינימלי מבין כל החלוקות ה-k-רציפות האפשריות.
הערה: הבעיה ניתנת לפתרון בעזרת תכנות דינמי.
סעיף א' (10 נקודות)
בהינתן מערך A בגודל N, מספר טבעי k ופונקציית עלות כללית C(i,j),
כתבו נוסחה רקורסיבית לחישוב העלות של מחיר החלוקה k-רציפה מינימלית. יש לפרט גם את מקרי הבסיס. יש לפרט את משמעות הנוסחה.
רמז: יש פתרון בעזרת 2 פרמטרים.
סעיף ב' (10 נקודות)
הראו אלגוריתם תכנות דינמי לפתירת בעיית החלוקה k-רציפה מינימלית.
סעיף ג' (5 נקודות)
מהו (א) זמן הריצה ומהו (ב) גודל המקום (זיכרון) של האלגוריתם שהצעתם בסעיף ב?