אתגר תכנותי: שודד הבתים

נותנים לך מערך המתאר את כמות הכסף שאפשר לגנוב מכל בית פרטי ברחוב. עליך למצוא את מירב הכסף שניתן לשדוד מהרחוב כאשר התנאי הוא שאסור לשדוד שני בתים סמוכים כי אם שודדים שני בתים סמוכים מופעלת אזעקה, ובאה המשטרה.

דוגמה לשווי הרכוש שניתן לשדוד מ-4 בתים:

houses = [2, 3, 4, 2]

המקסימום שניתן לשדוד הוא:

max_rob = 6

נסביר:

• אם שודדים את בתים 2 ו-4 מגיעים לסכום 2 + 3 = 5.
• אם שודדים את הבתים 1 ו-4 מגיעים לסכום 2 + 2 = 4.
• אם שודדים את בית 1 ו-3 (שאינם סמוכים) מגיעים למקסימום 2 + 4 = 6.

דוגמה נוספת:

houses = [3, 8, 10, 4, 2]

המקסימום שניתן לשדוד הוא:

max_rob = 15

כפי שמלמד החישוב הבא:

3 + 10 + 2 = 15

Brute Force פתרון

בפתרון "brute force" (כוח גס), אנו מנסים את כל השילובים האפשריים של בתים שניתן לשדוד, בתנאי שלא עוברים על תנאי האתגר, ואין שודדים שני בתים סמוכים.

נבחן את הדוגמה הבאה:

houses = [3, 8, 10, 4, 2]

על מנת למצוא את הסכום המקסימלי שניתן לשדוד, עלינו לבחון את כל הצירופים האפשריים:

• שוד של הבית הראשון בלבד: 3
• שוד של הבית הראשון והשלישי: 3 + 10 = 13
• שוד של הבית הראשון, השלישי והחמישי: 3 + 10 + 2 = 15
• שוד של הבית השני בלבד: 8
• שוד של הבית השני והבית הרביעי: 8 + 4 = 12
• שוד של הבית השלישי בלבד: 10
• שוד של הבית השלישי והחמישי: 10 + 2 = 12
• שוד של הבית הרביעי בלבד: 4
• שוד של הבית החמישי בלבד: 2

המסקנה היא שהשוד המקסימלי האפשרי הוא 15, כאשר שודדים את הבית הראשון, השלישי והחמישי.

כפי שניתן לראות, פתרון brute force אכן מוצא את התשובה הנכונה. היתרון בגישה זו הוא שהיא פשוטה להבנה ולמימוש, והיא תמיד מוצאת את התשובה הנכונה. עם זאת, החיסרון המשמעותי הוא שיש צורך לבחון את כל הצירופים האפשריים, דבר שיכול להפוך את החישוב ללא יעיל ככל שמספר הבתים גדל.

למשל, עבור רחוב עם n בתים, יש לבחון 2^n צירופים אפשריים, מכיוון שלכל בית יש שתי אפשרויות: לשדוד אותו או לא לשדוד אותו. המשמעות היא שעל כל בית נוסף, מספר הצירופים גדל בצורה מעריכית.

לדוגמה:

• עבור 10 בתים, יש לבחון 1024 צירופים.
• עבור 20 בתים, כבר יש לבחון למעלה ממיליון צירופים.

זו הסיבה שהפתרון הזה אינו מתאים לרצפים ארוכים של בתים ודורש משאבי חישוב גדולים.

שימוש באלגוריתם חמדן

האלגוריתם החמדן פועל כך שבכל שלב הוא בוחר את האפשרות הנראית הכי טובה באותו רגע. במקרה שלנו, את הערך הגבוה ביותר שניתן לשדוד בכל צעד.

נבחן את מערך הבתים הבא:

houses = [3, 8, 10, 4, 2]

האלגוריתם החמדן יבחר תחילה את הבית עם הערך הגבוה ביותר שהוא הבית השלישי ממנו ניתן לשדוד 10.

כיוון ששדד את הבית השלישי הוא לא יכול לשדוד את הבתים השני והרביעי. מה שמשאיר את אפשרות לבחור בבית הראשון או החמישי. האלגוריתם ייבחר בבית הראשון כיוון שערכו גבוה יותר (3).

בשלב זה, האפשרות היחידה הנותרת היא לשדוד את הבית האחרון שערכו 2:

10 + 3 + 2 = 15

האלגוריתם החמדן הצליח למצוא, במקרה זה, את הסכום המקסימלי של 15.

אבל ישנם מקרים בהם הגישה החמדנית אינה מניבה את התוצאה הטובה ביותר. לדוגמה, אם המערך הוא:

houses = [4, 7, 4]

האלגוריתם החמדן יבחר תחילה את הבית השני עם ערך של 7, מכיוון שזהו הערך הגבוה ביותר. אך בכך הוא יפספס את האפשרות לשדוד את הבית הראשון והשלישי, שאינם סמוכים, ויכולים להניב סכום גבוה יותר: 4 + 4 = 8.

במקרה זה, האלגוריתם החמדן הגיע לתוצאה שאינה אופטימלית. ולכן, המסקנה היא שאלגוריתם חמדן אינו תמיד הדרך הנכונה לפתרון הבעיה שעל הפרק, כיוון שהוא עלול להחמיץ פתרונות טובים יותר על ידי בחירה בערכים הגבוהים ביותר בכל שלב.

פתרון מבוסס תכנות דינאמי

תכנות דינמי (Dynamic Programming) הוא גישה לפתרון בעיות מורכבות באמצעות פירוק לבעיות משנה קטנות יותר. פותרים כל בעיית משנה פעם אחת בלבד, ושומרים את התוצאה כך שלא נצטרך לבצע שוב את אותם החישובים. גישה זו מייעלת את הפתרון ומביאה לחיסכון במשאבי מחשוב.

כדי לפתח פתרון מבוסס תכנות דינמי, נתחיל בזיהוי הבעיה הקטנה ביותר האפשרית ונמצא דרך לפתור אותה. את הגישה שבה השתמשנו לפתרון הבעיה הקטנה ניישם גם עבור בעיות גדולות יותר: נפתור שתי תתי-בעיות, לאחר מכן שלוש, וכך הלאה, בכל פעם נוסיף שלב עד לפתרון הבעיה כולה.

בבעיית השודד שלנו, המטרה היא למצוא את מירב הכסף שניתן לשדוד מבלי לשדוד שני בתים סמוכים. נתחיל בפתרון של הבעיה הקטנה ביותר, ונרחיב אותו בהדרגה לבעיות גדולות יותר:

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

במילים אחרות, לכל בית אנו צריכים להחליט האם לשדוד אותו יחד עם התוצאה שנמצאה עבור הבתים הקודמים שאינם סמוכים, או להישאר עם התוצאה של הבתים הקודמים (ללא הבית הנוכחי).

מימוש בפייתון

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

• dp[0] שווה לערך של הבית הראשון.
• dp[1] שווה לערך הגבוה מבין הבית הראשון והשני.
• החל מהבית השלישי, dp[i] יכיל את הערך הגבוה ביותר מבין: הסכום המקסימלי שנצבר בבית הקודם, או ערך הבית הנוכחי בתוספת הסכום שנצבר עד הבית הקודם-קודם.

from typing import List

def rob(houses: List[int]) -> int:
   if not houses:
       raise Exception("No houses to rob")
  
   len_houses = len(houses)
  
   # If there's only one house, rob it
   if len(houses) == 1:
       return houses[0]
  
   # Dynamic Programming list to hold the max robbing results for each step
   dp = [0] * len_houses
  
   # Fill in the cases for the first 2 robberies
   dp[0] = houses[0]
   dp[1] = max(houses[1], houses[0])
  
   # Rob the remaining houses
   for idx in range(2, len_houses):
       # Each step finds the maximum robbery results in the current iteration
       dp[idx] = max(houses[idx]+dp[idx-2] , dp[idx-1])
  
   # Return the concluding item of the dp array
   return dp[len_houses-1]

נבחן את הפתרון:

# Test cases
cases = [
   [6, 9], # 9
   [3, 7, 5], # 8
   [1, 2, 3, 1], # 4
   [2, 7, 9, 3, 1], # 12
   [0, 0, 0, 0], # 0
   [5, 1, 5, 1, 5], # 15
]

for case in cases:
    print(f"Street: {case} -> Max that can be robbed: {rob(case)}")

סיבוכיות הזמן והמרחב

• סיבוכיות זמן: O(N) — נדרש לעבור על כל אחד מ-N הבתים במערך, כאשר הפעולות בתוך הלולאה הן פעולות בזמן קבוע (השוואה ותוספת).
• סיבוכיות מקום: O(N) — עלינו לאחסן את התוצאות בכל אחד מהבתים במערך dp, ולכן השימוש בזיכרון גדל בקצב לינארי בהתאם לגודל המערך.

עם זאת, אפשר לשפר את הפתרון עוד יותר ולצמצם את סיבוכיות המקום ל-O(1) בלבד. נסביר זאת בחלק הבא.

פתרון מבוסס תכנות דינאמי יעיל יותר הדורש סיבוכיות מקום קבועה O(1)

ניתן לייעל עוד יותר את הפתרון מבוסס תכנות דינאמי אם במקום להשתמש במערך dp נשתמש בשני משתנים אחד בשביל הצעד הקודם ושני בשביל הצעד הנוכחי כפי שמדגים הקוד הבא:

def rob(houses: List[int]) -> int:
   if not houses:
       raise ValueError("No houses to rob")
  
   len_houses = len(houses)
  
   # If there's only one house, rob it
   if len(houses) == 1:
       return houses[0]
  
   # Initialize with the maximum that can be robbed from the first and second houses
   prev = houses[0]
   curr = max(prev, houses[1])
  
   # Rob the remaining houses
   for idx in range(2, len_houses):
       # Calculate the new maximum by deciding whether to rob the current house or not
       # Store the previous value before updating it
       temp = prev
       # Update prev to the current maximum value (without robbing the current house)
       prev = curr
       # Calculate the new max by deciding whether to rob the current house or skip it
       curr = max(prev, houses[idx] + temp)

   # Return the accumulated results
   return curr

נסביר:

1. אם יש רק בית אחד, השודד שודד אותו, וזהו. זה הפתרון.
2. אחרת, מאתחלים שני משתנים: prev עם הרווח מהבית הראשון ו-cur לאחסון הרווח המרבי משוד שני הבתים הראשונים.
3. לאחר מכן, לולאה רצה על יתר הבתים. בכל פעם שהיא רצה, מחליטים האם לשדוד את הבית הנוכחי בתוספת הרווחים שנצברו בבית הקודם-קודם (houses[idx] + temp) או לקחת את הרווחים שנצברו בבית הקודם (prev).
4. בתוך הלולאה, משתנה נוסף בשם temp מאחסן את הערך של prev לפני שהוא מתעדכן, כדי לשמור את הרווחים של הבית הקודם-קודם.

סיבוכיות זמן ומקום

• סיבוכיות זמן: O(N) — האלגוריתם עובר על כל בית במערך פעם אחת.
• סיבוכיות מקום: O(1) — במקום להשתמש במערך שלם לשמירת התוצאות, השתמשנו במשתנים התופסים מקום קבוע בזכרון.

הפתרון אינו דורש מבני נתונים נוספים (דוגמת רשימה) בשביל הפתרון ועל כן סיבוכיות הזמן שהוא דורש הינה קבועה O(1).

מדריכים נוספים שעשויים לעניין אותך

פתרון בעיות אופטימיזיציה באמצעות אלגוריתם חמדן

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

פתרון בעיית הקיטבג knapsack באמצעות תכנות דינמי

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים