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