צריך עזרה בבנית רקורסיה

[MorAdato]

צריך עזרה בבנית רקורסיה

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

 

[טום הוק]

נראה לי, בתור שלב ראשון צריך להחליט מה

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

 

[vinney]

נראה כמו וריאציה של knapsack problem

אם למדת אלגוריתמים חמדניים - אתה אמור לדעת מה לעשות

בפורום שפות תכנות הזכירו backtracking, זה יכול להיות כיוון טוב להתחלה.

 

[MorAdato]

לא למדתי

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

 

[vinney]

אולי תכתוב את האלגוריתם שלך?

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

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

 

[MorAdato]

האלגוריתם שלי

תנאי עצירה 1. כאשר אני מגיע לתת קבוצה שגודלה 0 וערך שלי גדול מ0 אני מחזיר 1- (לא נמצא תת קבוצה) 2.כאשר אני מגיע לתת קבוצה 0 וערך שלי קטן מ0 אני מחזיר0 (נמצא תת קבוצה ) 3. כאשר נמצא תת קבוצה אך לא הגעתי לכל התת קבוצות התוכנית אני בודק האם הערך )Vmin) גדול מ0 אני מחבר את המשקל של המקום i וקורא לפונקציה שוב כאשר אני מחסיר את הערך של האיבר i מ Vmin ואיבר אחד פחות ואז אני קורא לפונקציה שוב בלי לחסר אך עם איבר אחד פחות בשלב הבא אני בודק מה יותר קטן ושמור את האיבר היותר קטן במקרה וVmin קטן מ0 אני קורא לפונקציה עם איבר אחד פחות. בסוף אני מחזיר את הערך הנמוך