מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/בעיית תיק הגב/שאלה

גנב פורץ לחנות תכשיטים. בחנות יש $\displaystyle n$ פריטים. התכשיט ה$\displaystyle i$ בעל שווי $\displaystyle v_{i}$ שקלים ומשקל $\displaystyle w_{i}$ קילוגרמים. הגנב יכול לברוח כשעל גבו $\displaystyle w$ קילוגרמים לכל היותר.

שימו לב: הנח שכל המשקלים בשאלה (כל $\displaystyle w_{i}$ ו$\displaystyle w$) הנם שלמים חיוביים ממש.

אנא תאר (בהסבר מילולי ופסוודו-קוד) אלגוריתם יעיל למציאת הפריטים שעל הגנב לקחת כדי להביא למקסימום את ערך שללו. אנא הוכח את נכונות האלגוריתם ונתח את סיבוכיותו.

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