29-04-2013, 18:28
|
|
|
חבר מתאריך: 18.07.05
הודעות: 3,884
|
|
פתרון "בעיית הגנב"
נתקלתי בבעיה כזאת:
נתון אוסף פריטים, שלכל אחד שלוש תכונות: ערך, משקל וגודל. לגנב יש תיק שמוגבל בגודל
ובמשקל שהוא יכול לשאת. מטרתו של הגנב היא למקסם את הרווח ע"י בחירת פריטים שערכם
הכולל הוא הגבוה ביותר, כך שהפריטים הנבחרים יוכלו להיכנס לתיק )מבחינת מגבלות גודל
ומשקל(. לשם פשטות נתייחס למושג "גודל" כערך סקלרי.
ממשו את הפונקציה הבאה, אשר מקבלת את גודל התיק, המשקל שהוא יכול לשאת, ושלושה
מערכים באורך - sizes, weights, values -n שהתא ה-i בהם מייצג את הגודל, המשקל והערך של
הפריט ה- בהתאמה. הפונקציה מחשבת ומחזירה את הערך הכולל המקסימלי של תת הקבוצה של
הפריטים, שנכנסים לתיק תחת מגבלות המקום והמשקל.( ניתן להשתמש בפוקציות עזר)
public static int knapsack(int bagSize, int bagWeight, int[] sizes,int[] weights, int[] values
אשמח לעזרה (עדיפות בג'אווה )
|