חיתוך מקל במחיר מקסימלי

נתון מקל באורך n ס"מ.

אפשר לחתוך את המקל לחתיכות בגדלים שונים (בסנטימטרים שלמים). לכל גודל של חתיכה יש מחיר. המחירים נתונים במערך בגודל n+1 כך שבמיקום i נמצא המחיר לחתיכה בגודל i. התא הראשון (אינדקס 0) אינו משמעותי בשאלה זו. הערך (המחיר) בו הוא תמיד 0.

לדוגמא, המערך להלן מכיל את מחירי החתיכות של מקל באורך 8 ס"מ.

012345678
01310910171720

בהינתן מערך חד-ממדי, מלא במספרים שלמים חיוביים ממש, ומספר שלם חיובי ממש n המהווה את אורך המקל.

יש להחזיר את המחיר המקסימלי שאפשר להשיג על ידי חיתוך המקל ומכירת החתיכות שלו.

בדוגמא לעיל, המחיר המקסימלי הוא 23. כאשר חותכים את המקל לשלוש חתיכות:

אחת באורך 2 ועוד שתי חתיכות באורך 3 (3+10+10 = 23).

אם במערך המחירים היה שינוי, והמחיר של החתיכה באורך 1 היה 4, אז המחיר המקסימלי היה 32, על ידי חיתוך המקל לשמונה חתיכות באורך 1.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:
  • מערך המחירים אינו ממוין!
  • מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי.
  • אסור להשתמש במשתנים גלובליים (סטטיים)!
דוגמה 1:
קלט: 
prices = [0, 1, 3, 10, 9, 10, 17, 17, 20],
n = 8
פלט: 
23

הסבר: המחיר המקסימלי מתקבל על ידי חיתוך המקל לשלוש חתיכות: אחת באורך 2 (מחיר 3) ושתיים באורך 3 (מחיר 10 כל אחת). סך הכל: 3 + 10 + 10 = 23.

דוגמה 2:
קלט: 
prices = [0, 4, 3, 10, 9, 10, 17, 17, 20],
n = 8
פלט: 
32

הסבר: כאשר מחיר החתיכה באורך 1 הוא 4, כדאי לחתוך את המקל ל-8 חתיכות באורך 1. סך הכל: 8 × 4 = 32.

דוגמה 3:
קלט: 
prices = [0, 2, 5, 7, 8],
n = 4
פלט: 
10

הסבר: המחיר המקסימלי מתקבל על ידי חיתוך המקל לשתי חתיכות באורך 2 כל אחת. סך הכל: 5 + 5 = 10.

דוגמה 4:
קלט: 
prices = [0, 1, 1, 7],
n = 3
פלט: 
7

הסבר: המחיר המקסימלי מתקבל על ידי השארת המקל שלם (ללא חיתוך). מחיר: 7.

דוגמה 5:
קלט: 
prices = [0, 5],
n = 1
פלט: 
5

הסבר: המחיר המקסימלי מתקבל על ידי השארת המקל שלם (ללא חיתוך). מחיר: 5.

דוגמה 6:
קלט: 
prices = [0, 6, 10],
n = 2
פלט: 
12

הסבר: המחיר המקסימלי מתקבל על ידי חיתוך המקל לשתי חתיכות באורך 1 כל אחת. סך הכל: 6 + 6 = 12.

דוגמה 7:
קלט: 
prices = [0, 5, 8, 10, 12],
n = 3
פלט: 
15

הסבר: המחיר המקסימלי מתקבל על ידי חיתוך המקל לשלוש חתיכות באורך 1 כל אחת. סך הכל: 5 + 5 + 5 = 15.

דוגמה 8:
קלט: 
prices = [0, 5, 8, 12, 14, 16, 20],
n = 6
פלט: 
30

הסבר: המחיר המקסימלי מתקבל על ידי חיתוך המקל לשש חתיכות באורך 1 כל אחת. סך הכל: 6 × 5 = 30.

Loading...
נשמרLn 1, Col 1

קלט:

prices = [0, 1, 3, 10, 9, 10, 17, 17, 20],
n = 8

הפלט המבוקש:

23