אלגוריתמיקה - מציאת סכום האיברים הנותן תוצאה הכי קרובה למספר?

[Daniel]

נניח שיש לי רשימת איברים שהם מספרים:

10,40,70

אני רוצה לראות איך אני יכול לחבר/לחסר ביניהם כדי לקבל את התוצאה הכי קרובה למספר כלשהו - אפשר להשתמש בכל מספר פעם אחת ולא חייבים להשתמש בכולם (אגב - כל המספרים תמיד חיוביים וגדולים מ-0 וכך גם התוצאה הכי קרובה).

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

אני אעשה

70 - 10

(שזוהי יוצא 60, שזה הכי קרוב ל-58).

הסכום תמיד נמוך מהאיבר הכי גבוה.

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


מה שעלה בדעתי זאת שיטה שלוקחת הרבה מאוד משאבים יחסית.
נניח שיש 4 מספרים והמטרה היא X,
לכל מספר יש 3 מצבים - מופיע בחיבור, מופיע בחיסור, לא מופיע.
לא יכול להיות שכל המספרים מופיעים בחיסור כמובן (כי אז יוצאת תוצאה שלילית).
לכן יש (4 ^ 3 פחות 4 שזה בעצם 60) אפשרויות ראשוניות (פחות 4 כי יש 4 מצבים שבהם הכל מינוסים. עם איבר 1, עם 2 איברים, עם 3 ועם 4) ואז צריך לעבור אפשרות אפשרות ולחשב. בסופו של דבר זה יוצא כמות דיי גדולה של חישובים, השוואות, ואני צריך להריץ את הדבר הזה כמות גדולה של פעמים במהירות גבוהה.


תהיתי אם למישהו יש הצעות לדרך יעילה יותר.

מקווה שהבנתם את השאלה.

[יניב בן צבי]

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

[IgalSt]

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

אם לדוגמא יש לך
1,4,10,13,18,20
ואתה צריך להגיע ל-15 לצורך העניין, חבל לרוץ על כל האפשרויות.
אם אתה רוצה ש- 20-1=19, אז אפשר לנסות 20-4 או 18-1 ולראות מה יותר מתאים לך. ברור ש-20-4 מקרב אותך יותר, ובמקרה הזה אתה שוב בודק לפי אותו האלגוריתם.

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

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

[Shay Ben Moshe]

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

[Daniel]

נכתב במקור על ידי יניב בן צבי

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

לא הבנתי בדיוק למה התכוונת. זה חלק ממטרה יותר גדולה כאשר בחלק מהתכנון של דרך הפתרון נתקלתי בדבר זה.

Exa.co.il: אבל בסופו של דבר אני רץ על הכל כדי להיות בטוח (או עוצר כשאני מתרחק יותר) ואני מחפש משהו יותר יעיל...

אני לא רוצה כיצד עץ בינארי יעזור כאן לפתרון...

שיי: זה +/- איבר.
תזכור שאין תמיד 3 - יכול להיות 2 ויכול להיות 10. בכל מקרה, זה שדבר ראשון צריך למיין כמו ששניכם אמרתם, אני מסכים.
נניח שאני מסדר (סדר עולה).
אני יכול לקחת את האיבר הראשון, ונניח ש-p הוא המטרה, אז D = p - a1
אם p - a1 + a2 קטן יותר מ-D, אז D שווה לביטוי שכרגע הראיתי, וממשיך הלאה עם כל שאר האיברים. אם לא אז מנסה פעולה חיסור וממשיך. וחוזר חלילה. נראה לי הדרך הכי אינטואיטיבית שבן אדם יעשה.


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

[IgalSt]

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

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

[Shay Ben Moshe]

נכתב במקור על ידי MasterT

לא הבנתי בדיוק למה התכוונת. זה חלק ממטרה יותר גדולה כאשר בחלק מהתכנון של דרך הפתרון נתקלתי בדבר זה.

Exa.co.il: אבל בסופו של דבר אני רץ על הכל כדי להיות בטוח (או עוצר כשאני מתרחק יותר) ואני מחפש משהו יותר יעיל...

אני לא רוצה כיצד עץ בינארי יעזור כאן לפתרון...

שיי: זה +/- איבר.
תזכור שאין תמיד 3 - יכול להיות 2 ויכול להיות 10. בכל מקרה, זה שדבר ראשון צריך למיין כמו ששניכם אמרתם, אני מסכים.
נניח שאני מסדר (סדר עולה).
אני יכול לקחת את האיבר הראשון, ונניח ש-p הוא המטרה, אז D = p - a1
אם p - a1 + a2 קטן יותר מ-D, אז D שווה לביטוי שכרגע הראיתי, וממשיך הלאה עם כל שאר האיברים. אם לא אז מנסה פעולה חיסור וממשיך. וחוזר חלילה. נראה לי הדרך הכי אינטואיטיבית שבן אדם יעשה.


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

בהנחה שאתה עובר על כולם הסיבוכיות היא n^2 - n, בהנחה שאתה עובר עם רשימה עולה של המספרים על כל קומבינציות החיבור (מבלי לחזור על ביטויים שווים a+b b+a) והחיסור (אך אם עשית b-a לא תעשה a-b כיוון שהמספר או שללי או חיובי.
ניתן להוכיח בקלות לכל n:
למספר הראשון נחבר את כל הבאים אחריו (n - 1).
לשני נחבר את כל הבאים אחריו (n - 2).
...
לn - 2 נחבר את כל הבאים אחריו (2).
לn - 1 נחבר את כל הבאים אחריו (1).
לn לא נחבר דבר.
משמע הסכום הוא מk = 1 עד k = n-1 של k. סכום הסדרה הוא 1 + (n-1) כל זה כפול n-1 חלקי שתיים. במילים פשוטות (n^2 - n)/2.
זו ההוכחה לחיבור, לחיסור מתקיים או דבר, מהגדול ביותר מחסרים את כל השאר, מזה שאחריו את כל מי שתחתיו וכולי.
נחבר (n^2 - n)/2 ל(n^2 - n)/2 ונקבל n^2 - n.

כמה שאני אוהב מתמטיקה D:

[Shay Ben Moshe]

כתבתי פתרון שהסיבוכיות שלו היא בין n^2 - n (יותר קרוב לזה) לבין 2n - 2 (במקרים קיצוניים בלבד).
מה שהוא עושה זה מערך עם הנתונים.
עובר על קומבינציות החיבור ועל קומבינציות החיסור.
אני שומר משתנה זמני של ההפרש וההפרש האחרון כאשר הארגומנט הראשון זהה, אם ההפרש גדל אז אני קוטע את הלולאה וככה חוסך ריצות. מכיוון שPHP זו שפת מפרש אני לא יודע אם זה מועיל בה בכלל.
הפונקצייה מחזירה false למערך קטן מ2 אלמנטים או את האינדקס של הארגומנט הראשון והשני, את הסימן ביניהם ואת ההפרש מהתוצאה.
הקוד:

PHP קוד:

<?php

function find($array, $target) {
    if(count($array) < 2)
        return false;
    sort($array);
    $data = array(
        'diff'    => $target - $array[0] - $array[1],
        'arg1'    => 0,
        'arg2'    => 1,
        'opt'    => '+'
    );
    for($i = 0; $i < count($array); $i++) {
        $last_diff = null;
        for($j = $i + 1; $j < count($array); $j++) {
            $diff = abs($target - $array[$i] - $array[$j]);
            if(!is_null($last_diff) && $diff > $last_diff)
                break;
            if($diff < $data['diff']) {
                $data['opt'] = '+';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = $diff;
            }
            $last_diff = $diff;
        }
    }
    for($i = count($array) - 1; $i > 0; $i--) {
        $last_diff = null;
        for($j = $i - 1; $j >= 0; $j--) {
            $diff = abs($target - $array[$i] + $array[$j]);
            if(!is_null($last_diff) && $diff > $last_diff)
                break;
            if($diff < $data['diff']) {
                $data['opt'] = '-';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = $diff;
            }
            $last_diff = $diff;
        }
    }
    return $data;
}

נריץ:

PHP קוד:

print_r(find(array(10, 40, 70), 58)); 


הפלט:

PHP קוד:

Array
(
    [diff] => 2
    [arg1] => 2
    [arg2] => 0
    [opt] => -
) 


הצעות ליעול יתקבלו בברכה. (וכשכתבתי את זה בשעה כזו אני בטוח שתיהינה)

עריכה:
הפתרון בלי הוידוי של ההפרש (השוותי אותם, עם הוידוי יותר מהיר בגדול, ככל שיש יותר "מיותרים" ככה הוא יותר יעיל מן הסתם):

PHP קוד:

<?php

function find($array, $target) {
    if(count($array) < 2)
        return false;
    sort($array);
    $data = array(
        'diff'    => $target - $array[0] - $array[1],
        'arg1'    => 0,
        'arg2'    => 1,
        'opt'    => '+'
    );
    for($i = 0; $i < count($array); $i++) {
        for($j = $i + 1; $j < count($array); $j++) {
            if(abs($target - $array[$i] - $array[$j]) < $data['diff']) {
                $data['opt'] = '+';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = abs($target - $array[$i] - $array[$j]);
            }
        }
    }
    for($i = count($array) - 1; $i > 0; $i--) {
        for($j = $i - 1; $j >= 0; $j--) {
            if(abs($target - $array[$i] + $array[$j]) < $data['diff']) {
                $data['opt'] = '-';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = abs($target - $array[$i] + $array[$j]);
            }
        }
    }
    return $data;
}

[Daniel]

שיי, לצערי הרב לא בנתי את כוונתך. כאשר אני קורא לפונקציה בצורה הבאה:

PHP קוד:

find(array(10, 20, 30, 40), 100) 


הוא צריך להגיד לי לחבר את כולם כדי להגיע ל-100 לדוגמא.

ערך החזרה אפשרי יהיה לדוגמא:

PHP קוד:

array(1, 1, 1, 1); 


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

לדוגמא, אם הייתי קורא:

PHP קוד:

find(array(10, 50, 110), 36) 


אז הוא היה צריך להחזיר לי:

PHP קוד:

array(-1, 1, 0); 


כי:

PHP קוד:

(-1) * 10 + 1 * 50 + 0 * 110 = 40 


שזה הכי קרוב.

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

[Shay Ben Moshe]

אהה אני לא הבנתי אותך נכון.
הקוד שלי בודק את הקומבינציה של השניים הכי קרובים.