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

נניח שסדרת הפריטים מתוארת על ידי שתי סדרות: $\displaystyle V=[v_{1},...,v_{n}]$ המתארת את שווי הפריטים, ו$\displaystyle W=[w_{1},...,w_{n}]$ המתארת את משקליהם. נגדיר כ$\displaystyle m(V,W,w)$ את שווי המקסימום של פריטים תחת אילוץ המשקל: בצורה אחרת, מקסימום $\displaystyle \sum _{j=1}^{n'}[v_{i_{j}}]$,‏ תחת האילוץ ש$\displaystyle \sum _{j=1}^{n'}[w_{i_{j}}]\leq w$.‏

משפט: לכל שתי סדרות $\displaystyle V$ ו$\displaystyle W$, ושלם חיובי $\displaystyle w$: $\displaystyle m(V,W,w)=\max\{m(V',W',w-w_{i})+v_{i}),m(V',W',w)\}$, כאשר i הוא אורך הסדרות $\displaystyle V$ ו$\displaystyle W$, ו$\displaystyle V'$ ו$\displaystyle W'$ הן הסדרות המתקבלות מ$\displaystyle V$ ו$\displaystyle W$ בהתאמה ע"י השמטת האיבר האחרון. כמו כן, $\displaystyle m(V,W,-w)=-\infty$,‏ ו$\displaystyle m([],[],w)=0$.

הוכחה: #אם הגנב רואה את סדרות הפריטים $\displaystyle V$ ו$\displaystyle W$,‏ יש לו בדיוק שתי אפשרויות לגבי

 $\displaystyle w_{i}$:

 ##אם הגנב יבחר לקחת את הפריט ה$\displaystyle i$, אז כבר בשלב זה הוא ירוויח
   $\displaystyle v_{i}$
   ויהיה עליו לשאת $\displaystyle w_{i}$ קילוגרמים. עפ"י ההגדרה,
   השווי המקסימלי של שאר הפריטים שיוכל לשאת תחת
   מגבלת המשקל החדשה, הוא $\displaystyle m(V',W',w-w_{i})+v_{i}$.

   ##אם הגנב יבחר להשאיר את הפריט ה$\displaystyle i$, אז הפריט אינו משנה את
   רווחו או המשקל שהוא נושא. עפ"י ההגדרה, השווי המקסימלי
   של שאר הפריטים שיוכל לשאת, הוא $\displaystyle m(V',W',w)$.

1. כמו כן:

 ##$\displaystyle m(V,W,-w)=-\infty$,‏ מפני שמצב שבו הוא נושא יתר משקל פשוט אינו
   קביל, ונוכל לתרגם זאת לכך שנתן למצב זה מחיר שלילי
   אינסופי.

   ##$\displaystyle m([],[],w)=0$,‏ מפני שאם אין פריטים בחנות, הרווח בוודאי
   0.