מה המצב חברה
יש לי שאלה ברקורסיה שאני לא יודע איך לגשת אליה
אשמח שתעלו רעיונות לפיתרון

תודה

השאלה

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

קוד:

public static boolean isFillBag (int[] arr, int num)

אינכם רשאים לשנות את חתימת השיטה, אבל אתם יכולים להיעזר בשיטה נוספת פרטית שעושה
לשיטה זו. overload
אתם יכולים להניח שהמערך מלא במספרים שלמים חיוביים בלבד.
דוגמאות:

עבור M=10 ורשימת החפצים 20 3 10 1 14
השיטה תדפיס 10 יוחזר TRUE

עבור M=20 ורשימת החפצים 4 1 15 7 12 3 9
השיטה תדפיס 12 1 7 יוחזר TRUE

עבור M=12 ורשימת החפצים 18 5 3 11
יוחזר FALSE


השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות בכלל!

הנה פתרון שרשמתי בשפת C# , אני שם לב שאתה משתמש בג'אבה אך השפות דומות מאוד:

קוד PHP:

 public static bool isFillBag(int[] arr, int num)
{
    bool isTrue = false;

    for (int i = 0; i < arr.Length; i++)
        isTrue = isTrue || isFillBag(arr, num, i, 0, isTrue, string.Empty);

    return isTrue;
}

private static bool isFillBag(int[] arr, int num, int i, int count, bool isTrue, string series)
{
    if (i == arr.Length - 1)
        isTrue = isTrue || false;

    count += arr[i];
    series += arr[i] + " ";

    if (count > num)
        isTrue = isTrue || false;

    else if (count == num)
    {
        Console.Write(series);
        return true;
    }

    for (i = i+1;  i < arr.Length; i++)
        isTrue = isTrue || isFillBag(arr, num, i, count, isTrue, series);

        return isTrue;
} 


בשביל לקבל True או False וגם רשימת מספרים מתאימה, הדפס כך:

קוד:

int[] arr = { 14, 1, 10, 3, 20 };
Console.WriteLine(isFillBag(arr, 10));

תודה רבה על התשובה

אני אשמח שתסביר לי במילים איך לבצע את התרגיל
כדי שאני אכתוב אותו לבד

אני לא רוצה להעתיק את שלך

תודה

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

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות בכלל!

יש מצב שאתה יכול לחשוב על דרך אחרת

תודה

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

אני לא במין איך אתה רץ על כל המערך ובודק את כל האופציות

אשמח לתשובה יותר מפורטת

תודה

שאלה צדדית: האם אתה יכול להסביר את הפקודה

קוד:

isTrue = isTrue || false;

שחוזרת פעמיים בתוכנית?

עבור כל אחד מהאיברים במערך אתה רץ כמה שיותר ימינה, עד שמגיעים לאחד מתנאי העצירה הבאים:
1. נמצא רצף
2. הסתיימו כל הסריקות


בקשר לשאלה השניה, הפקודה הזאת מקבלת 'או' ( | | ) בשביל לא לפספס צירופים שהמרחק בניהם גדול מ-1. למשל, אם קיים מערך: { שש, חמש, ארבע, שתיים } ואני מנסה להגיע לצירוף 10, תתבצע בדיקה ראשונית 6+5 ותחזיר false - אך משום שאתה רוצה להמשיך ולבדוק, הביטוי מקבל 'או' עד שנבדקים כל האיברים או עד שנמצא רצף מסויים. זה מופיע פעמיים, אבל אני מאמין שאפשר איכשהו לוותר על פעם אחת, לא ניסיתי למצוא איך.

אני לא מצליח להגיע לבדיקה הגיונית
של כל הרצף..

אם יש לי מערך {40 ,4 ,6 ,12 ,1 ,20, 7}
40 זה הערך הראשון

אני רוצה לבדוק האם 14 נכנס פה??

אני בהתחלה בודק האם האיבר גדול מהמהספר אם כן חזר אחורה ומעלה את מיקום האיברים

הרצף הנכון צריך להיות 6,1,7

נגיד ועשינו את הבדיקות של 40 ו 4 על כל המערך ועשכיו אנחנו ב 6

הבדיקות הן

6+40 = 14 אם כן -נכון
אם לא 6+40 < 14 המשך אם לא זרוק את 40

6+4 = 14 אם כן - נכון
אם 6+4 < 14 המשך אם לא זרוק את 4

6+4+12 = 14 אם כן - נכון
אם לא 6+4+12 < 14 המשך אם לא זרוק את 12

6+4+1 = 14 אם כן - נכון
אם לא 6+4+1 < 14 המשך אם לא זרוק את 1

6+4+1+20 = 14 אם כן - נכון
אם לא 6+4+1+20 < 14 המשך אם לא זרוק את 20

6+4+1+7 = 14 אם כן - נכון
אם לא 6+4+1+7 < 14 המשך אם לא זרוק את 7

נשארתי עם 6+4+1 ופיספסתי את 6+1+7

תודה על העזרה

אתה אומר ש-40 הוא האיבר הראשון, אבל בפועל אתה מתקדם אחורה ולא קדימה.
נניח והגענו ל-6, מכן נפתחות 4 התפצלויות חדשות:
6+12
6+1
6+20
6+7
מכל התפצלות כזאת, נפתחות עוד 3 התפצלויות (והלאה, עוד 2, עוד 1, עד לבדיקת כל הצירופים האפשריים).
ברגע שצירוף אחד יחזיר true, הרקורסיה תסתיים ותחזיר את הרצף שנשמר.

רשמתי ש 40 זה האיבר הראשון

פשוט רשמתי את המערך הפוך

אבל בכל זאת אני לא הבנתי את כל ההתפצלויות שרשמת

אנה יכול להראות לי את זה בצורה יותר מופשטת

תודה

אין קשר לאיך שרשמת את המערך, אם אתה מתחיל לבדוק מ-6 אתה אמור לרוץ שמאלה (לפי איך שרשמת את המערך).
זאת אומרת, הגענו ל-6, ואז נבדוק:
18 = 12 + 6
7 = 1 + 6
26 = 20 + 6
13 = 7 + 6

כעת כל צירוף מתפצל. הצירופים 1 ו-3 כבר עברו את הסכום המבוקש (14) ולכן קיבלו false.
אך שם לב שצירופים 2 ו-4 ממשיכים. צירוף מספר 4 יתפצל ויקבל false, אך בוא נבדוק מה קורה עם צירוף מספר 2. כעת הוא מתפצל כך:
27 = 20 + 1 + 6
14 = 7 + 1 + 6

הצירוף הראשון קיבל false, אך הצירוף השני קיבל true והחזיר את הרצף שלו.

מה זה אומר כל צירוף מתפצל???

מה המצב חברה
חייב עזרה עם התרגיל
אני לא כל כך הבנתי את ההסבר של trialusert

זה אומר שנפתחת רקורסיה חדשה לאותו צירוף.

זה הולך להיות קשה
את הרעיון של הרקורסיה אני יודע

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

כי בעוד שני איברים יש ערך מתאים יותר
דוגמה

6,3,4,10,1,13,6,4,8,9

6 איבר 0

המספר 15

הצירוף 6+4+1+4

בהתחילה 6+3 < 15
ממשיך

בגלל ש 3 הוא לא מספר שבגללו אנחנו עוברים את הסכום הרצוי אני לא מצליח לא לחשב אותו

תודה

אז זהו, ההתחלה היא לא רק
3 + 6
ההתחלה היא
3 + 6
4 + 6
10 + 6
1 + 6
...
וזאת הכוונה בהתפצלות, כל מספר שהגענו מתפצל לעוד x מספרים. מבין?

וואו...
אוקי

אז מה שאתה אומר זה הולך להיות ככה...

זה המערך שלנו 6,3,4,10,1,13,6,4,8,9

3 + 6 = 9
4 + 6 = 10
10 + 6 = 16
1 + 6 = 7
...

מצטער שאני משגע אותך פשוט זה לא נקלט לי... (;

כל מספר שהגענו מתפצל לעוד x מספרים .... איך בדיוק??
אשמח לתשובה מיספרית כמו בדוגמא למעלה

תודה

בדיוק כמו ש-6 התפצל. לפי הדוגמה שלך, אני ממשיך:

התפצלות של 9:
4 + 9
10 + 9
1 + 9
...

התפצלות של 10:
4 + 10
10 + 10
1 + 10
...

התפצלות 16:
4 + 16
10 + 16
1 + 16
...

התפצלות 7:
4 + 7
10 + 7
1 + 7
...

וכך הלאה...

הבעיה היא שבסכום 10
התפצלות של 10:
4 + 10
10 + 10
1 + 10
...
4 כבר קיים
המקור היה 6+4

שמע, אתה עושה את זה הרבה יותר מסובך ממה שזה. ההתפצלויות שרשמתי מקודם הן של הסכומים, הכוונה היתה ל-10 של ה: 4 + 6

יש לך מסנג'ר / איסיקיו ? יהיה לי קל יותר להסביר לך...

בוא נעשה את זה יותר קל

תנסה לתקן לי את הקוד

תודה

אולי ככה אני אבין (לפי הקוד שלי)

קוד PHP:

 static int arrPosition = 0;
    static boolean answer = false;
    public static boolean isFillBag(int[] arr, int num)
    {
        if(arr[arrPosition] == arr.length)
        {
            return answer;
        }
        else if(arr[arrPosition] == num)
        {
            System.out.println(arr[arrPosition]);
            answer = true;
            return answer;
        }
        else if(arr[arrPosition] < num)
        {
            int count = arr[arrPosition];
            String values = "" + arr[arrPosition];
            int position = 0;
            boolean isTrue = false;
            answer = isFillBag(arr, num, position, count, isTrue, values);
        }
        if(!answer)
        {
            arrPosition++;
            answer = isFillBag(arr, num);
        }
        return answer;
    }
    
    public static boolean isFillBag(int[] arr, int num, int position, int count, boolean isTrue, String values)
    {
        if(position == arr.length)
        {
            return isTrue;
        }
        else
        {
            count += arr[position];
            values += arr[position] + " ";
            
            if(count == num)
            {
                System.out.println(values);
                isTrue = true;
                return isTrue;
            }
            else if(count < num)
            {
                position++;
                isTrue = isFillBag(arr, num, position, count, isTrue, values);
            }
            else
            {
                isTrue = false;
            }
            return isTrue;
        }
    } 


יש לך הרבה בדיקות מיותרות, המשתנים הסטטיים מיותרים, והפעולה השנייה אמורה להיות פרייבט... מקווה שתבין את השינויים:

קוד:

public static boolean isFillBag(int[] arr, int num)
{
	boolean isTrue = false;

	for (int i = 0; i < arr.length; i++)
		isTrue = isTrue || isFillBag(arr, num, i, 0, false, "");

	return isTrue;
}

private static boolean isFillBag(int[] arr, int num, int position, int count, boolean isTrue, String values)
{
	count += arr[position];
	values += arr[position] + " ";

	if (count == num)
	{
		Console.WriteLine(values);
		return true;
	}
	if (count < num)
	{
		for (int i = 0; i < arr.length; i++)
			isTrue = isTrue || isFillBag(arr, num, i, count, isTrue, values);
	}

	return isTrue;
}

סבבה אבל אני צריך את זה בלי לולאות

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

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

אשמח שתעיף מבט

תודה

קוד PHP:

 public class ifFillBag 
{
    static int arrPosition = 0;
    static boolean answer = false;
    public static boolean isFillBag(int[] arr, int num)
    {
        if(arrPosition == arr.length)
        {
            return answer;
        }
        else if(arr[arrPosition] == num)
        {
            System.out.println(arr[arrPosition]);
            answer = true;
            return answer;
        }
        else if(arr[arrPosition] < num)
        {
            int count = arr[arrPosition];
            String values = arr[arrPosition] + " ";
            int position = 0;
            boolean isTrue = false;
            answer = isFillBag(arr, num, arrPosition, position, count, isTrue, values);
        }
        if(!answer && arrPosition < arr.length)
        {
            arrPosition++;
            answer = isFillBag(arr, num);
        }
        return answer;
    }
    
    private static boolean isFillBag(int[] arr, int num, int arrPosition, int position, int count, boolean isTrue, String values)
    {
        if(position == arr.length)
        {
            return isTrue;
        }
        else
        {
            if(position == arrPosition)
            {
                position++;
                isTrue = isFillBag(arr, num, arrPosition, position, count, isTrue, values);
            }
            else if(count == num)
            {
                System.out.println(values);
                isTrue = true;
                return isTrue;
            }
            else if(count < num)
            {                
                count += arr[position];
                if(count <= num)
                {                    
                    values += arr[position] + " ";
                }
                else
                {
                    count -= arr[position];
                }
                position++;
                isTrue = isFillBag(arr, num, arrPosition, position, count, isTrue, values);
            }
            else
            {
                position++;
                isTrue = isFillBag(arr, num, arrPosition, position, count, isTrue, values);
            }
            
            if(position < arr.length)
            {
                position++;
                isTrue = isFillBag(arr, num, arrPosition, position, count, isTrue, values);
            }
            
            return isTrue;
        }
    }
}