Skip to main content

Posts

Showing posts from August, 2017

What is dynamic programming (hebrew)?

תכנון דינמי, תכנות דינמי או באנגלית Dynamic Programming הם שמות לדרך ליצירת אלגוריתמים. המילה "תכנות" בשם כוונות יצירת תוכנית פעולה ולא קידוד בשפת תכנות.
הבסיס של השיטהשני הרעיונות שעומדים מאחורי השם המרשים הם:
1.האלגוריתם יפתור את הבעייה בצורה רקורסיבית ע"י חלוקתה לתתי בעיות שגם הן נפתרות ע"י חלוקתן לתתי בעיות וכו עד שמגיעים לבעיה פשוטה. זה בעצם סוג של רקורסיה עם כמה תוספות.
2.החזקה בצד את כל התוצאות שכבר נמצאו לתתי בעיות כך שאם נגיע שוב לאותה תת בעייה, לא נחשב אותה שוב.
יותר קל להבין את הרעיון הזה ע"י שתי דוגמאות. דוגמא אחת היא בעיית "תרמיל הגב" ובעייה שנייה היא חישוב מספר פיבונצ'י.
בעיית "תרמיל הגב"  בעיית "תרמיל הגב" או Knapsack problemהיא בעייה כללית שיש לה שימושים שונים. 
דוגמא לבעיה הזו: גנב נכנס למחסן. יש לו תרמיל שיכול לסחוב עד 7 ק"ג. במחסן יש 30 מוצרים. כל מוצר שוקל משקל מסויים ויש לו ערך כספי מסויים. הגנב צריך דרך (אלגוריתם) לדעת איזה מוצגים לקחת כך שיהיה להם את הערך הכספי המירבי אך שמשקלם הכולל יהיה לכל היותר 7 ק&…