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