שאלה ממבחן 2014
mustKnow (guest) 01 Jul 2014 21:02
שאלה 5
נתונות ערים, על גבי ישר. בין כל שתי ערים נתון המרחק בליטרים )מספר שלם(. כמו כן, בכל עיר
קיימת תחנת דלק עם מחיר כלשהוא לליטר דלק, שבה הנהג יכול לתדלק. לנהג יש מכל דלק המכיל לכל היותר
ליטרים. הראו כיצד ניתן לחשב כיצד להגיע מהעיר הראשונה לעיר במחיר מינימאלי , כשבמיכל יש r ) (
ליטרים לפני שהוא יוצא לדרך. חשבו את הסיבוכיות זמן הריצה של האלגוריתם. כמובן שכדי לעבור מעיר לעיר
הבאה צריך שיהיה במיכל לפחות כמות ליטרים כמרחק ביניהם.
אשמח לעזרה
