בעיית התרמיל
שיעור 7 מתוך 15 בקורס תכנות דינמי 101 של Coddy.
בעיית התרמיל היא בעיית אופטימיזציה קלאסית במדעי המחשב. ניסוח הבעיה פשוט: בהינתן קבוצה של פריטים, שלכל אחד מהם משקל וערך, יש לקבוע אילו פריטים לכלול באוסף כך שהמשקל הכולל יהיה קטן ממגבלה נתונה או שווה לה, והערך הכולל יהיה מרבי.
ישנם שני סוגים של בעיית התרמיל:
- תרמיל 0/1: בגרסה זו, הגנב אינו יכול לקחת חלקי פריט; הוא יכול לקחת את הפריט בשלמותו או להשאיר אותו.
- תרמיל שברי: בגרסה זו, הגנב יכול לקחת חלקי פריט, כלומר, אפשר לקחת חלק מפריט.
אתגר
בינוניכתבו פונקציה בשם knapsack שפותרת את בעיית התרמיל 0/1. הפונקציה צריכה לקבל שלושה קלטים:
- רשימת המשקלים של n פריטים (w1, w2, ... , wn).
- רשימת הערכים של n פריטים (v1, v2, ... , vn).
- קיבולת המשקל המרבית של התרמיל (W).
לאחר מכן, הפונקציה צריכה להחזיר את הערך המרבי שאפשר להשיג ממילוי התרמיל.
לדוגמה:
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
knapsack(weights, values, W)פלט:
220 # taking the 2 largest itemsנסו בעצמכם
def knapsack(wrights, values, W):
# כתבו כאן את הקודכל השיעורים ביחידה תכנות דינמי 101
תרגלו בעצמכם: קומפיילר Python אונליין