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

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $\displaystyle m_{1},m_{2},\ldots m_{n}$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

1. מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_{i}$ רווחיה הצפויים יהיו $\displaystyle p_{i}$ ‏($\displaystyle p_{i}$ הוא מספר חיובי כלשהו).
2. הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ$\displaystyle k$‏ ($\displaystyle k$ הוא מספר שלם חיובי כלשהו).

דוגמה: אם $\displaystyle k=20$ והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן $\displaystyle 143-135<20$.

אנא כתוב אלגוריתם יעיל המקבל את המערך M (המכיל את מספרי הבתים), את המערך P (המכיל את הרווחים הצפויים), ואת המספר k (המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.