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

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

ישנם שני סוגים של בעיות תרמיל:

• 0/1 בעיית תרמיל
• בעיה בתרמיל חלקי

נדון בשתי הבעיות אחת לאחת. ראשית, נלמד על בעיית תרמיל 0/1.

מהי בעיית תרמיל 0/1?

בעיית הכנאפה של 0/1 פירושה שהפריטים הם לגמרי או שאין פריטים ממולאים בתרמיל. לדוגמה, יש לנו שני פריטים במשקל של 2 ק'ג ו-3 ק'ג, בהתאמה. אם נבחר את הפריט של 2 ק'ג אז לא נוכל לבחור פריט של 1 ק'ג מהפריט של 2 ק'ג (הפריט אינו ניתן לחלוקה); אנחנו צריכים לבחור את הפריט של 2 ק'ג לחלוטין. זוהי בעיית תרמיל 0/1 שבה או שנבחר את הפריט לגמרי או שנבחר את הפריט הזה. בעיית התרמיל 0/1 נפתרת על ידי התכנות הדינמי.

מהי בעיית התרמיל השברירי?

בעיית התרמיל השברירי פירושה שאנו יכולים לחלק את הפריט. לדוגמה, יש לנו פריט של 3 ק'ג ואז נוכל לבחור את הפריט של 2 ק'ג ולהשאיר את הפריט של 1 ק'ג. בעיית הכנאפה השברית נפתרת על ידי הגישה החמדנית.

דוגמה לבעיית 0/1 תרמיל.

שקול את הבעיה שיש משקלים ורווחים הם:

משקלים: {3, 4, 6, 5}

רווחים: {2, 3, 1, 4}

משקל הכנאפה 8 ק'ג

מספר הפריטים הוא 4

ניתן לפתור את הבעיה שלעיל באמצעות השיטה הבאה:

איקס_אני= {1, 0, 0, 1}

= {0, 0, 0, 1}

מה גודל מסך המסך שלי

= {0, 1, 0, 1}

האמור לעיל הם השילובים האפשריים. 1 מציין שהפריט נבחר לחלוטין ו-0 פירושו שאף פריט לא נבחר. מכיוון שיש 4 פריטים אז שילובים אפשריים יהיו:

2⁴= 16; כך. ישנם 16 שילובים אפשריים שניתן לבצע באמצעות הבעיה שלעיל. לאחר ביצוע כל השילובים, עלינו לבחור את השילוב המספק את הרווח המקסימלי.

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

כיצד ניתן לפתור בעיה זו באמצעות גישת התכנות הדינמי?

ראשון,

אנו יוצרים מטריצה ​​המוצגת להלן:

במטריצה ​​שלמעלה, עמודות מייצגות את המשקל, כלומר, 8. השורות מייצגות את הרווחים והמשקלים של פריטים. כאן לא לקחנו ישירות את המשקל 8, הבעיה מחולקת לתת-בעיות, כלומר, 0, 1, 2, 3, 4, 5, 6, 7, 8. פתרון הבעיות המשנה יישמר ב- התאים והתשובה לבעיה יאוחסנו בתא הסופי. ראשית, נכתוב את המשקולות בסדר עולה ואת הרווחים לפי משקלם המוצג להלן:

ב_אני= {3, 4, 5, 6}

ע_אני= {2, 3, 4, 1}

השורה הראשונה והעמודה הראשונה יהיו 0 מכיוון שאין פריט עבור w=0

כאשר i=1, W=1

ב₁= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל 3, אבל הקיבולת של הכנאפה היא 1. אנחנו לא יכולים למלא את הפריט של 3 ק'ג בתרמיל של קיבולת 1 ק'ג אז הוסף 0 ב-M[1][1] שמוצג להלן :

כאשר i = 1, W = 2

ב₁= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל 3, אבל הקיבולת של הכנאפה היא 2. אנחנו לא יכולים למלא את הפריט של 3 ק'ג בתרמיל בנפח של 2 ק'ג אז הוסף 0 ב-M[1][2] שמוצג להלן :

כאשר i=1, W=3

ב₁= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא גם 3; לכן, נוכל למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר 2 ב-M[1][3] שמוצג להלן:

כאשר i=1, W=4

_W1= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא 4; לכן, נוכל למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר, 2 ב-M[1][4] שמוצג להלן:

כאשר i=1, W=5

_W1= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא 5; לכן, אנו יכולים למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר, 2 ב-M[1][5] המוצג להלן:

כאשר i=1, W=6

_W1= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא 6; לכן, נוכל למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר, 2 ב-M[1][6] שמוצג להלן:

כאשר i=1, W=7

_W1= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא 7; לכן, אנו יכולים למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר, 2 ב-M[1][7] שמוצג להלן:

כאשר i = 1, W = 8

_W1= 3; מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-3, ומשקל התרמיל הוא 8; לכן, נוכל למלא את התרמיל בפריט במשקל השווה ל-3. אנו שמים רווח המקביל למשקל 3, כלומר 2 ב-M[1][8] שמוצג להלן:

כעת הערך של 'i' גדל והופך ל-2.

כאשר i = 2, W = 1

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-4, ומשקל הכנאפה הוא 1. אנחנו לא יכולים לשים את הפריט במשקל 4 בתרמיל, אז נוסיף 0 ב-M[2][1 ] מוצג להלן:

כאשר i = 2, W = 2

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו רק פריט אחד בסט עם משקל שווה ל-4, ומשקל הכנאפה הוא 2. אנחנו לא יכולים לשים את הפריט במשקל 4 בתרמיל, אז נוסיף 0 ב-M[2][2 ] מוצג להלן:

כאשר i = 2, W = 3

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 3. אנחנו יכולים לשים את הפריט במשקל 3 בתרמיל, אז נוסיף 2 ב-M[2][3] מוצג להלן:

כאשר i = 2, W = 4

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 4. אנו יכולים לשים פריט במשקל 4 בתרמיל שכן הרווח המקביל למשקל 4 הוא יותר מהפריט בעל המשקל 3, אז נוסיף 3 ב-M[2][4] שמוצג להלן:

כאשר i = 2, W = 5

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 5. אנחנו יכולים לשים פריט במשקל 4 בתרמיל והרווח המתאים למשקל הוא 3, אז נוסיף 3 ב- M[2][5] מוצג להלן:

כאשר i = 2, W = 6

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 6. אנחנו יכולים לשים פריט במשקל 4 בתרמיל והרווח המתאים למשקל הוא 3, אז נוסיף 3 ב- M[2][6] מוצג להלן:

כאשר i = 2, W = 7

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 7. אנחנו יכולים לשים פריט במשקל 4 ו-3 בתרמיל והרווחים המקבילים למשקלים הם 2 ו-3; לכן, הרווח הכולל הוא 5, אז נוסיף 5 ב-M[2][7] שמוצג להלן:

כאשר i = 2, W = 8

המשקל המתאים לערך 2 הוא 4, כלומר, w₂= 4. מכיוון שיש לנו שני פריטים בסט עם משקלים 3 ו-4, ומשקל הכנאפה הוא 7. אנחנו יכולים לשים פריט במשקל 4 ו-3 בתרמיל והרווחים המקבילים למשקלים הם 2 ו-3; לכן, הרווח הכולל הוא 5, אז נוסיף 5 ב-M[2][7] שמוצג להלן:

כעת הערך של 'i' גדל, והופך ל-3.

כאשר i = 3, W = 1

מתמטיקה אקראית java

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט עם משקלים 3, 4 ו-5, ומשקל הכנאפה הוא 1. אנחנו לא יכולים לשים אף אחד מהפריטים בתרמיל, אז נוסיף 0 ב-M[3][ 1] מוצג להלן:

כאשר i = 3, W = 2

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט עם משקל 3, 4 ו-5, ומשקל הכנאפה הוא 1. אנחנו לא יכולים לשים אף אחד מהפריטים בתרמיל, אז נוסיף 0 ב-M[3][ 2] מוצג להלן:

כאשר i = 3, W = 3

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה ומשקל הכנאפה הוא 3. ניתן להכניס את הפריט במשקל 3 לתרמיל והרווח המתאים לפריט הוא 2, אז נוסיף 2 ב-M[3][3] שמוצג להלן:

כאשר i = 3, W = 4

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה, ומשקל התרמיל הוא 4. אנחנו יכולים לשמור את הפריט במשקל 3 או 4; הרווח (3) המתאים למשקל 4 הוא יותר מהרווח המתאים למשקל 3 ולכן נוסיף 3 ב-M[3][4] שמוצג להלן:

כאשר i = 3, W = 5

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה, ומשקל התרמיל הוא 5. אנחנו יכולים לשמור את הפריט במשקל 3, 4 או 5; הרווח (3) המתאים למשקל 4 הוא יותר מהרווחים התואמים את המשקל 3 ו-5 ולכן נוסיף 3 ב-M[3][5] המוצג להלן:

כאשר i = 3, W = 6

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה, ומשקל התרמיל הוא 6. אנחנו יכולים לשמור את הפריט במשקל 3, 4 או 5; הרווח (3) המתאים למשקל 4 הוא יותר מהרווחים התואמים את המשקל 3 ו-5 ולכן נוסיף 3 ב-M[3][6] המוצג להלן:

כאשר i = 3, W = 7

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה, ומשקל התרמיל הוא 7. במקרה זה, נוכל לשמור גם את הפריטים במשקל 3 ו-4, סכום הרווח יהיה שווה ל-(2 + 3), כלומר 5, אז נוסיף 5 ב-M[3][7] שמוצג להלן:

כאשר i = 3, W = 8

המשקל המתאים לערך 3 הוא 5, כלומר, w₃= 5. מכיוון שיש לנו שלושה פריטים בסט של משקל 3, 4 ו-5 בהתאמה, ומשקל התרמיל הוא 8. במקרה זה, נוכל לשמור גם את הפריטים במשקל 3 ו-4, סכום ה- הרווח יהיה שווה ל-(2 + 3), כלומר 5, אז נוסיף 5 ב-M[3][8] המוצג להלן:

כעת הערך של 'i' גדל והופך ל-4.

כאשר i = 4, W = 1

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל הכנאפה הוא 1. משקל כל הפריטים הוא יותר ממשקל הכנאפה, כך שאיננו יכולים להוסיף כל פריט בתרמיל; לכן, אנו מוסיפים 0 ב-M[4][1] המוצג להלן:

כאשר i = 4, W = 2

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל הכנאפה הוא 2. משקל כל הפריטים הוא יותר ממשקל הכנאפה, כך שאיננו יכולים להוסיף כל פריט בתרמיל; לכן, אנו מוסיפים 0 ב-M[4][2] שמוצג להלן:

כאשר i = 4, W = 3

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל הכנאפה הוא 3. ניתן להכניס את הפריט במשקל 3 לתרמיל והרווח מתאים ל- משקל 4 הוא 2, אז נוסיף 2 ב-M[4][3] שמוצג להלן:

כאשר i = 4, W = 4

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל הכנאפה הוא 4. ניתן להכניס את הפריט במשקל 4 לתרמיל והרווח מתאים ל- משקל 4 הוא 3, אז נוסיף 3 ב-M[4][4] שמוצג להלן:

כאשר i = 4, W = 5

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל הכנאפה הוא 5. ניתן להכניס את הפריט במשקל 4 לתרמיל והרווח מתאים ל- משקל 4 הוא 3, אז נוסיף 3 ב-M[4][5] שמוצג להלן:

כאשר i = 4, W = 6

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בערכת המשקולות 3, 4, 5 ו-6 בהתאמה, ומשקל התרמיל הוא 6. במקרה זה, נוכל לשים את הפריטים בתרמיל כל אחד במשקל 3, 4 , 5 או 6 אבל הרווח, כלומר 4 המקביל למשקל 6 הוא הגבוה ביותר מבין כל הפריטים; לכן, אנו מוסיפים 4 ב-M[4][6] שמוצג להלן:

כאשר i = 4, W = 7

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקלים 3, 4, 5 ו-6 בהתאמה, ומשקל התרמיל הוא 7. כאן, אם נוסיף שני פריטים של משקלים 3 ו-4 אז זה יפיק את המקסימום רווח, כלומר (2 + 3) שווה ל-5, אז נוסיף 5 ב-M[4][7] המוצג להלן:

כאשר i = 4, W = 8

הפליקסר שלי

המשקל המתאים לערך 4 הוא 6, כלומר, w₄= 6. מכיוון שיש לנו ארבעה פריטים בסט המשקלים 3, 4, 5 ו-6 בהתאמה, ומשקל התרמיל הוא 8. כאן, אם נוסיף שני פריטים של משקלים 3 ו-4 אז זה יפיק את המקסימום רווח, כלומר (2 + 3) שווה ל-5, אז נוסיף 5 ב-M[4][8] המוצג להלן:

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

שוב, נשווה את הערך 5 מהשורה שלמעלה, כלומר, i = 2. מכיוון שהשורה שלמעלה מכילה את הערך 5, כך שהמצביע שוב יוסט כלפי מעלה כפי שמוצג בטבלה הבאה:

שוב, נשווה את הערך 5 מהשורה שלמעלה, כלומר, i = 1. מכיוון שהשורה שלמעלה אינה מכילה את אותו ערך אז נשקול את השורה i=1, והמשקל המתאים לשורה הוא 4. לכן. , בחרנו את המשקל 4 ודחינו את המשקולות 5 ו-6 המוצגות להלן:

x = { 1, 0, 0}

הרווח המתאים למשקל הוא 3. לכן, הרווח הנותר הוא (5 - 3) שווה ל-2. כעת נשווה את הערך הזה 2 עם השורה i = 2. מכיוון שהשורה (i = 1) מכילה את הערך 2 ; לכן, המצביע הוזז כלפי מעלה המוצג להלן:

שוב נשווה את הערך 2 עם שורה למעלה, כלומר, i = 1. מכיוון שהשורה i =0 אינה מכילה את הערך 2, אז שורה i = 1 תיבחר והמשקל המתאים ל-i = 1 מוצג 3 לְהַלָן:

X = {1, 1, 0, 0}

הרווח המתאים למשקל הוא 2. לכן, הרווח הנותר הוא 0. אנו משווים ערך 0 עם השורה שלמעלה. מכיוון שהשורה שלמעלה מכילה ערך 0 אך הרווח המקביל לשורה זו הוא 0. בבעיה זו נבחרים שני משקלים, כלומר 3 ו-4 כדי למקסם את הרווח.