אפשר עזרה בבקשה? אני צריך למצוא

[גוקר בקרוקר]

אפשר עזרה בבקשה? אני צריך למצוא

knapsack problem המתאים לשאלה ששאלתי...חיפשתי בGOOGLE ולא מצאתי את הקוד המתאים... אשמח אם תוכלו לעזור לי לחפש נתון תרמיל גב המסוגל לעמוד בעומס של num ק"ג, ונתונים X חפצים אותם רוצים לקחת לטיול. עבור כל אחד מהחפצים נתון משקלו. צריך לבדוק האם קיים צירוף כלשהו של חפצים המאפשר לנצל במלואו את העומס המותר לתרמיל. כתבו שיטה רקורסיבית בוליאנית המקבלת כפרמטרים את העומס המותר של התרמיל - num ומערך שיכיל את משקלות החפצים. השיטה תחזיר ערך true אם ניתן לאסוף חפצים במשקל זהה לעומס המותר לתרמיל ו- false אם לא. כמו כן, השיטה תדפיס גם את משקלות החפצים המקיימים את התנאי (אם יש כאלה). אם יש יותר מצירוף אחד - יודפס אחד מהם. חתימת השיטה - public static boolean isFillBag (int[] arr, int num) אינכם רשאים לשנות את חתימת השיטה, אבל אתם יכולים להיעזר בשיטה נוספת פרטית שעושה overload לשיטה זו. אתם יכולים להניח שהמערך מלא במספרים שלמים חיוביים בלבד. דוגמאות: 1. עבור M = 10 ורשימת החפצים 14 20 3 10 1 יוחזר true והשיטה תדפיס 10 2. עבור M = 20 ורשימת החפצים 9 3 12 7 15 1 4 יוחזר true והשיטה תדפיס (למשל) 12 7 1 3. עבור M = 12 ורשימת החפצים 11 3 5 18 יוחזר false. השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות בכלל!

 

[vinney]

השאלה אומרת

"כתבו", לא "מצאו". אתה אמור לכתוב את הקוד, לא למצוא אותו בגוגל. כשאמרו לך לחפש knapsack problem, התכוונו שתחפש פתרון דומה כדי להבין מה אתה אמור לעשות, לא לחפש פתרון מוכן להגשה.

 

[גוקר בקרוקר]

ברור לי...

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

 

[גוקר בקרוקר]

אפשר עזרה בבקשה? כיצד עליי להמשיך?

 

[גוקר בקרוקר]

תענו כברררררררררררררררררר

 

[1ca1]

כמו שאמרו לך

דבר ראשון זה לא הknapsack במובל הרגיל (בד"כ יש גם שני knapsacks, האם מותר לקחת שברים או רק 0-1 knapsack), שהוא מדבר על הקומבינציה שמביאה לך הכי הרבה משקל מנוצל. אתה מדבר למעשה על הsubset-sum (רשמתי עליה כאן למטה לפני כמה ימים). בגדול תממש פונקציית עזר שכשאתה נותן לה וקטור עם האינקדסים שבחרת לקחת אומרת לך האם היא קטנה מהסכום הכולל, שווה לו, או גדולה ממנו. עכשיו, ההיגיון הוא כזה, אתה עובר בצורה רקורסיבית על כל תתי-הקבוצות האפשריות מתוך X הפריטים. לכל תת קבוצה, אתה מריץ את פונקצייתת העזר הזאת. אם מצאת שהסכום הכולל גדול מהמשקל, תחזיר false ותצא לענף אחר ברקורסיה. אם מצאת שהסכום הכולל שווה למשקל,תדפיס את הערכים ותחזיר true (וכמובן בכל מקום ברקורסיה, אם החזרת true, תפעפע את זה למעלה). אחרת, הסכום הכולל קטן מהמשקל הנתון, אז תוסיף איבר אחד מאלה שנשארו (זאת בעצם לולאה להריץ שכל פעם תיבחר איבר אחר מאלה שנשארו), ולהריץ את הפונקציה הרקורסיבית על הוקטור הזה.

 

[h a j b i]

מועד ההגשה של המטלה הזאת כבר מזמן עבר, לא?

 

[גוקר בקרוקר]

לא...

זה ל-12.01.08