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

-------------------------

אוקי, סבבה. בניתי שיטה, אבל כשאני קוראת לה עם פונ' הדפסה, אני מקבלת תמיד FALSE. אני יוצאת מדעתי!!
הנה הקוד:

קוד:

  public static boolean isFillBag (int[] arr, int num)
	{
	  return isFillBag(arr, num, arr.length); 
	}
   
	
   
	private static boolean isFillBag(int[] arr, int num, int len)
	{
		if(num==0)
			return true;
		
		 else 
		 {
			 if(len>0 && num>=0)
			 {
				 if(isFillBag(arr, num-arr[len-1], len-1))
					System.out.print(arr[len-1]);
				isFillBag(arr, num, len-1);
			}
		 }
	 
		return false;
	}

והנה האתחול והקריאה מהמיין:

קוד:

 int arr[]={1, 10, 3, 20, 14};
	
	
				 System.out.print( isFillBag(arr, 10));   

עזרו לי בבקשה, אני משתגעת מהדבר הזה!
תודה

אני חושב שזה צריך להיות ככה:

קוד:

	private static boolean isFillBag(int[] arr, int num, int len)
	{
		if(num==0)
			return true;
		
		 else 
		 {
			 if(len>0 && num>=0)
			 {
				 if(isFillBag(arr, num-arr[len-1], len-1)) {
						System.out.print(arr[len-1]);
						return true;
					}
					if (isFillBag(arr, num, len-1)) 
						return true;
				}
		 }
	 
		return false;
	}

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

מבחינת יעילות זאת אותה היעילות...

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

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

קוד:

package rec;

public class rec {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr={1,3,14,50,60,4};
		String str="";
		System.out.println(isFillBag(arr,75,0,str));
		//System.out.println(isFillBag2(arr,75,arr.length));  
		
	}
	
	 public static boolean isFillBag (int[] arr, int num, int l,String str){
		 if (num==0){
			 System.out.println(str);
			 return true;
		 }
		 if (l==arr.length || num<0)
			 return false;
		 return isFillBag (arr,num-arr[l],l+1,str+ " " +arr[l])||
		 	isFillBag (arr,num,l+1,str);
	 }

}

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

בברכה, מתן.
www.MatanNarkiss.com

אבל זו לא בעית הגנב..
מה שכן, זו בעיה שאפשר לפתור ע"י רדוקציה לבעית הגנב.. (מחיר כל פריט=משקלו).
קיים פתרון לבעיה <=> מחיר האופט של הרדוקציה=משקל הרצוי.