יישום בעיות כנאפה בג'אווה

1. הקדמה

בעיית הכנאפה היא בעיית אופטימיזציה קומבינטורית שיש בה יישומים רבים. במדריך זה נפתור בעיה זו ב- Java.

2. בעיית הכנאפה

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

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

לכן עלינו לבחור את הפריטים שמשקלם הכולל אינו חורג ממגבלת המשקל, וערכם הכולל גבוה ככל האפשר. לדוגמא, הפיתרון הטוב ביותר עבור הדוגמה לעיל הוא לבחור בפריט 5 ק"ג ובפריט 6 ק"ג, מה שנותן ערך מקסימלי של 40 $ במסגרת מגבלת המשקל.

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

3. הגדרה מתמטית

בואו נתבונן כעת בבעיית הכנאפה 0-1 בסימון מתמטי. ניתנה סט של נ פריטים ומגבלת המשקל W, אנו יכולים להגדיר את בעיית האופטימיזציה כ:

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

4. פתרון רקורסיבי

אנו יכולים להשתמש בנוסחת רקורסיה כדי לפתור בעיה זו:

בנוסחה זו, M (n, w) הוא הפיתרון האופטימלי עבור נ פריטים עם מגבלת משקל w. זהו המקסימום של שני הערכים הבאים:

  • הפיתרון האופטימלי מ (n-1) פריטים עם מגבלת המשקל w (לא כולל נפריט -th)
  • ערך ה- נ-פריט בתוספת הפיתרון האופטימלי מ- (n-1) פריטים ו w משקל מינוס של נפריט (כולל נפריט -th)

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

אנו יכולים ליישם את נוסחת הרקורסיה הזו ב- Java:

int knapsackRec (int [] w, int [] v, int n, int W) {if (n W) {return knapsackRec (w, v, n - 1, W); } אחר {להחזיר Math.max (knapsackRec (w, v, n - 1, W), v [n - 1] + knapsackRec (w, v, n - 1, W - w [n - 1])); }} 

בכל שלב של רקורסיה עלינו להעריך שני פתרונות לא אופטימליים. לכן זמן הריצה של פתרון רקורסיבי זה הוא O (2n).

5. פתרון תכנות דינמי

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

אנחנו יכולים גם לפתור את בעיית הכנאפה 0-1 בתכנות דינמי. כדי להשתמש בתכנות דינמי, ראשית אנו יוצרים טבלה דו ממדית עם ממדים בין 0 ל נ ו 0 ל W. לאחר מכן אנו משתמשים בגישה מלמטה למעלה כדי לחשב את הפתרון האופטימלי באמצעות טבלה זו:

int knapsackDP (int [] w, int [] v, int n, int W) {if (n <= 0 || W <= 0) {return 0; } int [] [] m = int int [n + 1] [W + 1]; עבור (int j = 0; j <= W; j ++) {m [0] [j] = 0; } עבור (int i = 1; i <= n; i ++) {for (int j = 1; j j) {m [i] [j] = m [i - 1] [j]; } אחר {m [i] [j] = Math.max (m [i - 1] [j], m [i - 1] [j - w [i - 1]] + v [i - 1]); }}} להחזיר m [n] [W]; } 

בפתרון זה, יש לנו לולאה מקוננת על מספר הפריט נ ומגבלת המשקל W. לכן זמן הריצה הוא O (nW).

6. מסקנה

במדריך זה הראינו הגדרה מתמטית לבעיית הכנאפה 0-1. ואז סיפקנו פתרון רקורסיבי לבעיה זו ביישום Java. לבסוף השתמשנו בתכנות דינמי כדי לפתור בעיה זו.

כמו תמיד, קוד המקור של המאמר זמין באתר GitHub.