אנו מגדירים פריט (Item) כעצם (אובייקט) שיש לו שתי תכונות: משקל (weight_) וערך (value_).
להלן ההגדרה של המחלקה Item:
נתון מערך חד-ממדי items מלא באובייקטים מהמחלקה Item, לכל אובייקט במערך יש משקל וערך.
כמו כן, נתון תרמיל גב (knapSack) שהקיבולת (capacity) שלו היא w, כלומר, אי אפשר להכניס לתרמיל פריטים במשקל כולל שהוא גדול מ-w.
עלינו להחליט אילו פריטים כדאי להכניס לתרמיל הגב, כך שהערך של הפריטים האלה יהיה מקסימלי (וכמובן לא להכניס יותר מהקיבולת של התרמיל).
בהינתן מערך של אובייקטים מהמחלקה Item ומשקל w (מספר שלם), יש להחזיר מה הערך המקסימלי שאפשר להשיג מהאובייקטים שבמערך, כך שמשקלם הכולל לא יעלה על w.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
אין צורך לכתוב מהם הפריטים שנלקחים אלא רק את ערכם הכולל.
אפשר להניח שהמערך מלא בנתונים תקינים.
items = [[10, 60], [20, 100], [30, 120], [15, 200]], w = 30
260
הסבר: כדאי לקחת את הפריטים 0 ו-3 כי ערכם הכולל הוא 260 בעוד ששני הפריטים שבמקומות 0 ו-1 ערכם הוא רק 160.
items = [[10, 60], [20, 100], [30, 120], [15, 200]], w = 50
360
הסבר: • אם קיבולת התרמיל היא w = 50, אז כדאי להכניס את הפריטים שבתאים 0, 1 ו- 3, וכך הערך המקסימלי יהיה 360.
items = [[5, 10], [3, 15], [8, 20]], w = 0
0
items = [[5, 100]], w = 10
100
items = [[15, 100]], w = 10
0
items = [[1, 1], [2, 3], [3, 4], [4, 7], [5, 9]], w = 8
13
items = [[25, 50], [30, 80], [15, 40], [20, 70], [10, 30]], w = 60
180
items = [[5, 15], [10, 25], [15, 35]], w = 30
75
קלט:
items = [[10, 60], [20, 100], [30, 120], [15, 200]], w = 30
הפלט המבוקש:
260