התרגיל הוא ככה:

ישנן חמש משקולות, כאשר לכל משקולת יש משקל ומחיר.

אם המשקל גבוה, זה לא אומר בהכרח שהמחיר גבוה. כלומר ייתכן שמשקולת של 2 ק"ג תעלה 10 ש"ח ומשקולת של 8 ק"ג תעלה 4 ש"ח.

בנוסף יש תיק אשר מסוגל לסחוב מקסימום 15 ק"ג. כלומר הוא יכול להכיל משקל השווה ל-15 ק"ג או קטן ממנו.

עליך לכתוב פונקציה המקבלת כפרמטרים שני מערכים של משקלים ומחירים ואת גודל המערכים. (prices מותאם למשקולת שמשקלה weights).

על הפונקציה להחזיר את המחיר המקסימלי של משקולות שניתן לסחוב בתיק.

דוגמא להצהרה של הפונקציה ב-C++:

int MaxPrice(int weights[], int prices[], int arr_length)

ניתן לפתור את זה ברקורסיה.

אתם מוזמנים לנסות לפתור (אני מתעניין ברעיונות שונים לפיתרון, אין צורך במימוש)

זוהי פראפרזה על בעיית התרמיל (Knapsack problem) .

במקרה הזה הבעייה היא מהסוג הפשוט: בדיד, דטרמיניסטי, סופי ובעל אילוץ אחד.

רשום בעיית אופטימיזציה ליניארית למקסימום הרווח עם אילוץ אחד על המשקל הכולל.

קירוב טוב ניתן למצוא ע"י חישוב אינדקס עלות/משקל לכל פריט וסידור הפריטים לפי האינדקס.

בעיה מסוג הבעיות הראשונות שמתנסים בפתרונן כשלומדים backtracking, כאשר העיקרון הוא לבדוק את כל אפשרויות מילוי התיק (תחת מגבלות המשקל ומספר סופי של משקולות), ולהעריך לבסוף מהו המחיר הגבוה ביותר שחושב מכל נסיונות ההצבה בתיק.

השתמשתי כאן באותה חתימה של הפונקציה שנתת, מלבד הוספת bag המקבל את תכולת התיק בק"ג.

דוגמא לפתרון:

int MaxPrice(int weights[], int prices[], int arr_length,int bag){
	int res1=0,res2=0;
	if ((bag<=0)||(arr_length<=0))
		return 0;

	if (bag>=weights[0]){
		res1=prices[0]+MaxPrice(weights+1, prices+1, arr_length-1,bag-weights[0]);
	}
	res2=MaxPrice(weights+1, prices+1, arr_length-1,bag);
	return (max(res1,res2));
}

int max(int a, int b){
	return (a>b ? a : b);
}

נראה לי שרוב הזמן הפתרון שאני הייתי מעדיף הוא בעזרת תכנות דינמי. הוא פשוט יחסית למימוש (ולכן גם סבירות נמוכה יחסית לבאגים), יעיל יחסית בזמן, נותן פתרון מדוייק, ובד"כ בזבוז הזכרון שהוא דורש הוא מחיר נמוך עבור היתרונות.

אני מציע לך להתחיל בwikipedia וגוגל, זו בעיה ידועה היטב ושימושית, ולכן נחקרה לא מעט.