בעיית התרמיל
שיעור 7 מתוך 15 בקורס אתגרי רקורסיה – שליטה בחשיבה רקורסיבית של Coddy.
אתגר
בינוניבעיית התרמיל היא בעיה מפורסמת.
בבעיה הזאת יש לך תרמיל שמוגדר מראש המשקל שהוא יכול לשאת, ופריטים שלכל אחד מהם יש משקל וערך.
המשימה שלך היא לקחת ערך רב ככל האפשר, בגבולות המשקל של התרמיל.
לדוגמה,
ערכים - [20, 5, 40, 10, 15]
משקלים - [1, 2, 8, 3, 7]
משקל התרמיל - 10
הפתרון הוא לקחת את הפריטים שמשקליהם 1 ו-8 וערכיהם 20 ו-40.
הערך המרבי הוא 60, והמשקל הכולל הוא 9 (שהוא קטן מ-10 או שווה לו, כלומר זהו משקל תקין).
כתבו פונקציה בשם knapsack שמקבלת מספר שלם W ושני מערכים של מספרים שלמים values ו-weights, ומחזירה את הפתרון לבעיית התרמיל באמצעות ערכי הקלט (הערך המרבי שהתרמיל יכול לשאת).
נסו בעצמכם
#include <stdio.h>
#include <stdlib.h>
int knapsack(int W, int* values, int values_size, int* weights, int weights_size) {
// כתבו כאן את הקוד
return 0;
}
כל השיעורים ביחידה אתגרי רקורסיה – שליטה בחשיבה רקורסיבית
תרגלו בעצמכם: קומפיילר C אונליין