בעיית תרמיל הגב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←אלגוריתמי קירוב: ההוכחה שכתב משתמש:זה ינחמנו הייתה נכונה (למעט אי-דיוק קטן ולא משמעותי). ניסחתי בצורה יותר מפורטת, אולי מפורטת מדי... |
מ ←אלגוריתמי קירוב: עמוד בקובץ המקושר |
||
שורה 62:
=== אלגוריתמי קירוב ===
[[אלגוריתם חמדן|האלגוריתם החמדן]] הבא מוצא תרמיל שמחירו לכל הפחות מחצית המחיר של הפתרון המיטבי (2-קירוב){{הערה|Alexander Souza, [https://pdfs.semanticscholar.org/1788/27014a29983305b13f49b6a516fb791a9acf.pdf Combinatorial Algorithms - Lecture Notes , Winter Term 10/11], page 40, 2011}}:
נמיין את העצמים (שמשקלם אינו גדול מהחסם; עצם שמשקלו גדול מהחסם <math>W</math> אינו רלוונטי לבעיה) לפי יחס המחיר-משקל שלהם <math>p_i/w_i</math>. נוסיף לתרמיל, כל עוד זה אפשרי, את העצם הבא ברשימה הממוינת לפי יחס מחיר-משקל (מתחילים עם העצם בעל היחס הגבוה ביותר). נסמן ב-<math>j</math> את מספר העצמים שהצלחנו להכניס בצורה זו, ולכן ניתן לתאר את המחיר של העצמים שהכנסנו על ידי: <math>\sum_{i=1}^j p_i</math>. כעת נתבונן על המחיר של העצם ה-<math>j+1</math>: {{כ}}<math>p_{j+1}</math>. אם <math>\sum_{i=1}^j p_i > p_{j+1}</math>, נשאיר את <math>j</math> העצמים בתיק, ואם <math>\sum_{i=1}^j p_i < p_{j+1}</math>, נוציא את <math>j</math> העצמים מהתיק, ונכניס במקומם את העצם ה-<math>j+1</math>.
| |||