בעיית הכנאפה השברית ב-C++ מתייחסת לזיהוי דרך למלא שקית בפריטים בעלי משקל ורווח נתון באופן שהשקית מכילה את הערך המקסימלי מבלי לחרוג מהמגבלה המקסימלית.
כיצד לפתור את בעיית חפצי ה-Napsack ב-C++
בהינתן סט של פריטים, שלכל אחד מהם המשקל והרווח הנתון, קבעו כל מספר פריטים בשילוב כזה שהמשקל הכולל של הפריטים קטן מהמגבלה המקסימלית של התיק, אך יש לשמור על הערך גדול ככל האפשר.
אלגוריתם ליישום בעיית ה-Napsack השברירי
ניתן להבין את תפקודו של אלגוריתם Knapsack באמצעות הנקודות הבאות:
- קח שני מערכים של משקל ורווח.
- הגדר את ערך השק המרבי ל-W.
- קבע את הצפיפות על ידי לקיחת היחס בין שני הפרמטרים.
- מיין פריטים בסדר יורד של צפיפות.
- הוסף ערכים עד שהוא <=W.
הגישה החמדנית לפתרון בעיית החפצים השבריריים
הגישה החמדנית שואפת לעשות בחירות אידיאליות בכל שלב, מה שמוביל לפתרון האידיאלי בסופו. זה פותר בעיות צעד אחר צעד המוביל למסקנות במקום להסיק את התוצאות בסופו של דבר בלבד. זהו קוד מקור ליישום פתרון לבעיית הכנאפה השברית ב-C++:
#include
באמצעות מרחב שמות סטד ;
struct לְהִתְנַגֵד {
int ערך, משקל ;
לְהִתְנַגֵד ( int ערך, int מִשׁקָל )
: ערך ( ערך ) , משקל ( מִשׁקָל )
{
}
} ;
bool cmp ( struct אובייקט x, struct אובייקט י )
{
לְהַכפִּיל A1 = ( לְהַכפִּיל ) איקס. ערך / איקס. מִשׁקָל ;
לְהַכפִּיל A2 = ( לְהַכפִּיל ) ו. ערך / ו. מִשׁקָל ;
לַחֲזוֹר A1 > A2 ;
}
לְהַכפִּיל חלקי חנק ( struct חפץ arr [ ] ,
int IN, int גודל )
{
סוג ( arr, arr + גודל, cmp ) ;
int CurWeight = 0 ;
לְהַכפִּיל ערך סופי = 0.0 ;
ל ( int אני = 0 ; אני < גודל ; אני ++ ) {
אם ( CurWeight + arr [ אני ] . מִשׁקָל <= IN ) {
CurWeight + = arr [ אני ] . מִשׁקָל ;
ערך סופי + = arr [ אני ] . ערך ;
}
אַחֵר {
int לְהִשָׁאֵר = IN - CurWeight ;
ערך סופי + = arr [ אני ] . ערך
* ( ( לְהַכפִּיל ) לְהִשָׁאֵר
/ arr [ אני ] . מִשׁקָל ) ;
לשבור ;
}
}
לַחֲזוֹר ערך סופי ;
}
int ב = 60 ;
חפץ arr [ ] = { { 100 , עשרים } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int גודל = מידה של ( arr ) / מידה של ( arr [ 0 ] ) ;
cout << 'רווח מקסימלי = '
<< חלקי חנק ( arr, v, size ) ;
לַחֲזוֹר 0 ;
}
בקוד זה, מוגדר מבנה אובייקט אשר מאוחסנים בו ערכי משקל ורווח. ה-bool cmp() משמש לביצוע השוואה בין שני אובייקטים על בסיס היחס בין משקל וערך של שני אובייקטים. המערך מסודר בסדר יורד והערך ממשיך להתווסף עד שהוא מגיע למקסימום. אם הערך הנוכחי מותר ובגבול, הוא מתווסף, אחרת היחס המופחת שלו מתווסף לתיק. גודל המשקל והערך מוקלט בקוד הראשי והרווח המקסימלי מודפס על הפלט.
הרווח המקסימלי שהיה מאוחסן בחטיף הוא 580.
סיכום
בעיית הכנאפה השברית ב-C++ מתייחסת לזיהוי דרך למלא שקית בפריטים בעלי משקל ורווח נתון באופן שהשקית מכילה את הערך המקסימלי מבלי לחרוג מהמגבלה המקסימלית. ניתן להשיג זאת על ידי הגישה החמדנית שמטרתה לבצע בחירות אידיאליות בכל שלב, מה שמוביל לפתרון האידיאלי בסופו.