אם אחד המטבעות גדול או שווה ל 50 אחוז מחיבור של המטבע מעליו והמטבעות מתחתיו האלגוריתם החמדני לא יהיה אופטימלי1. בבעית העודף - החזרת מספר מטבעות מינימלי לסכום מסוים- האם יש איזושהי נוסחה פשוטה לדעת עבור סט ספציפי של מטבעות האם האלגוריתם החמדני הינו אופטימלי? (האם זה נכון שמספיק לבדוק רק עד המכנה המשותף המצומצם לגודל המטבעות? ואם כן- מדוע?)
לדוג עבור 1,2,5,10 - האלג' אופטימלי, ועבור 1,4,5 - לא אופטימלי
בשביל להרחיב את זה לפערים גדולים צריך לעשות כךאם אחד המטבעות גדול או שווה ל 50 אחוז מחיבור של המטבע מעליו והמטבעות מתחתיו האלגוריתם החמדני לא יהיה אופטימלי
כך נראה לי ממבט ראשון
תיקנתי בהודעה הבאהבשביל להרחיב את זה לפערים גדולים צריך לעשות כך
לבדוק את כמות הפעמים שנכנס האיבר באיבר שמעליו עם עיגול ללמעלה
ואת סכום העיגול לבדוק במטבעות כלפי מטה ולחבר את סכום המטבעות הקטנים שנכנסים בו עם המטבע הגדול מהאיבר ועושים ממוצע - אם זה קטן מהאיבר אז האלגוריתם החמדני לא יעבוד
גדול ולא שונהלפי זה - החמדני כן יעיל ל 9, 4, 2, 1:
9 + 2 + 1 (3) = 12 - חמדני
4 + 4 + 4 (3) = 12 - דינאמי
5, 4, 1:
4 נכנס ב 5 1.25 פעמים = 2.
5 + 1 + 1 + 1 (4) = 8. סך האיברים שונה מ 2, ואכן הוא לא יעיל כאן.
הפתרון האופטימלי הוא 4 + 4
ולפי זה ניתן להשתמש בחמדני ולעשות המרה רק לאפשרות של העיגול במקרה של 1,4,9 המרה של כל (9,1,1,1) ל (4,4,4)תיקון:
יש לבדוק את מספר המטבעות בחמדני של עיגול ללמעלה של חלוקת האיבר באיבר הגדול ממנו מול הסכום המעוגל השלם
אם החמדני גדול הוא לא יעיל
לדוג'
1,4,9
אז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא 3
מטבעות (9,1,1,1=4) > עיגול (3)
=לא יעיל (9,1,1,1) מול (4,4,4) = 12
לעומת זאת
1,2,4,9
ואז זה הולך כך
4 נכנס ב 9 2.25 = מעגלים ל3
הפער הוא =3
מטבעות (9,2,1=3) שווה(אותו דבר בקטן) עיגול (3)
= יעיל (9,2,1) מול (4,4,4) = 12
1,3,5 אופטימלילא הצלחתי ממש להבין.
לפי הנוסחא שלך - האם 1,3,5 אופטימלי או לא?
ו1,2,5,10,20,25?
ואותו סט של 6 המטבעות לעיל + מטבע של 15?
ב VBA1,3,5 אופטימלי
כך
5לחלק ל3 = 1.67 מעוגל ל2 (*3=6)
חמדני 6 = 1,5(2)
העיגול = 2 אז שניהם שווים וממילא החמדני - אופטימלי
1,2,5,10,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
20 לחלק ל 10 = 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,10,5 (3)
העיגול =2 אז החמדני גדול מהעיגול והוא לא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני לא אופטימלי
1,2,5,10,15,20,25
2)
5 לחלק ל2 = 2.5 מעוגל ל3 (*2=6)
חמדני 6 = 1,5 (2)
העיגול=3 אז החמדני קטן מהעיגול והוא אופטימלי - לאיבר זה
5)
10 לחלק ל5 = 2 (*5=10)
חמדני 10 = 10 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
10)
15 לחלק ל 10 = 1.5 מעוגל ל 2 (*10=20)
חמדני 20 = 20 (1)
העיגול = 2 אז החמדני קטן מהעיגול והוא אופטימלי לאיבר זה
15)
20 לחלק ל 15 = 1.333 מעוגל ל2 (*15=30)
חמדני 30 = 25,5 (2)
העיגול = 2 חמדני שווה לעיגול ולכן הוא אופטימלי לאיבר זה
20)
25 לחלק ל20 = 1.25 מעוגל ל2 (*20=40)
חמדני 40 = 25,15 (2)
העיגול =2 אז החמדני שווה לעיגול והוא אופטימלי לאיבר זה
וממילא בסט מטבעות זה החמדני אופטימלי
Option Compare Database
Function OptimalChamdani(ParamArray SetMatbeot()) As Boolean
Dim Temp1, Temp2
Dim TempIgul As Long
For Each i In SetMatbeot()
Temp2 = IIf(IsEmpty(Temp1), 0, Temp1)
Temp1 = i
If Temp2 > 0 Then TempIgul = Int((((Temp1 / Temp2)) / 1) + 0.999999)
If Not Chamdani(TempIgul * Temp2, SetMatbeot()) <= TempIgul Or Chamdani < 0 Then Exit Function
Next i
OptimalChamdani = True
End Function
Function Chamdani(Ms As Double, ParamArray SetMatbeot()) As Long
Dim Mone As Long, Total As Double, TempMone As Double
TempMone = -1
Do Until Total = Ms
If TempMone = Total Then GoTo Chelki
TempMone = Total
Total = Total + MaxInArray(Ms - Total, SetMatbeot)
Mone = Mone + 1
Loop
Chamdani = Mone
Exit Function
Chelki:
Chamdani = -1
End Function
Function MaxInArray(Agbala As Double, ParamArray SetMatbeot()) As Double
Dim i, Temp
Temp = 0
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i > Temp And i <= Agbala Then Temp = i
Next i
MaxInArray = Temp
End Function
Function MinInArray(ParamArray SetMatbeot()) As Double
Dim i, Temp
Temp = 0
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i > Temp Then Temp = i
Next i
For Each i In SetMatbeot(0)(0)
If IsNull(i) Then i = 0
If i < Temp And i > 0 Then Temp = i
Next i
MinInArray = Temp
End Function
בדוגמא ,1,4,9היי
מקווה שיש מישהו שיענה לי עכשיו....
הנוסחה נראית מדהימה, והיא גם מתיישבת על ההיגיון (אני הגעתי למשהו די דומה)
אבל זאת לא הוכחה שאפשר לכתוב במבחן., בעצם זאת לא הוכחה בכלל....
יש העיקרון דרך להוכיח אלגוריתמים חמדניים שמבוססת על הנחה שיש שאלגוריתם כלשהו הבוחר את הפתרון האופטימלי (במקרה הזה 0 מינימום המטבעות), אחר כך מניחים שהפלט של שתיהם (החמדן והאחר) זהה עד לנקודה מסויימת (שיכולה להיות גם הנקודה האפס ), ומשם והלאה הם שונים.
עד כאן ההנחות וכאן צריך להוכיח שניתן להחליף את הבחירה של האחר במקום השונה הראשון בבחירה של החמדני בלי לפגוע בנכונות הפלט, ואחר כך ניתן להחליף במקום הבא וכך הלאה - כלומר הפלט עדיין ישאר אופטימלי גם לאחר שיוחלף כולו לפלט של החמדן ומכאן שהחמדן הוא אופטימלי.
הבעיה היא שיש בעיות שפשוט מאד להוכיח את זה ויש בעיות (כמו בעיית העודף עם המטבעות 1,3,5) שזה יותר מורכב.
יש מישהו שמכיר את הדרך הזאת ויודע לתת לי הוכחה לבעייה הזאת עם הקלט הזה?
זה לא הוכחה מלאהלא יודעת אם קראת את כל מה שכתבתי קודם, אבל אני צריכה ניסוח פורמלי למבחן, ועכשיו מצאתי פתרון לבעיה דומה בדרך המבוקשת, אני מעתיקה אותו בשינויים קלים. מומלץ לקרוא כי זה מסדר את העניין הזה בראש...
הוכחה לבעיית המטבעות עבור כל קלט:
נשים לב:
א - כל אלג' יעיל שפותר את הבעיה ישתמש ב 2 מטבעות של 1 לכל היותר, כי 3 מטבעות של 1 ניתן להחליף במטבע 3
ב-כל אלג' יעיל שפותר את הבעיה ישתמש ב מטבע 1 של 3 לכל היותר, כי 2 מטבעות של 1 ניתן להחליף במטבעות 5,1 (בחירה חמדנית)
נמיין את המטבעות שבחרו האלגוריתמים מהגדול לקטן וניגש למקום הראשון שבו הבחירה הייתה שונה (שוב, ייתכן שזהו המקום הראשון) ונסמן את הבחירה של החמדן כ-X, ואת הבחירה של החמדן כ-Y
מכיוון שהחמדן בוחר בכל פעם את המטבע הגדול ביותר האפשרי, ברור ש X>Y
אם כן:
נניח ש X=5
האחר יחליף את הבחירה הזאת במטבע אחד של 3 ו-2 מטבעות של 1 - סב"כ 3 מטבעות - וזה וודאי פחות יעיל ממטבע אחד של 5.
נניח ש X=3
האחר יחליף את הבחירה ל 2 מטבעות של 1 (הרי הוכחנו שאף אלגוריתם יעיל לא יבחר יותר מ 2 מטבעות של 1)
ואם כן נותרנו עם סכום של 1 שהאלגוריתם האחר לא יכול לשלם, וזה מבטל את נכונות האלג האחר
אם אף אלג אחר לא יוכל למצוא בחירה טובה יותר מהחמדן, מוכח שהחמדן מביא את הבחירה הטובה ביותר.
(השורה הטיפשית והמובנת מאליה שצריך בסוף כל הוכחה...)
תנסה את זה על כל צרוף של מטבעות, פשוט מושלם!
בזמן שאתם מחפשים את החמץ, הלקוחות שלכם מחפשים אתכם בנרות!
מנוי פרימיום באתר פרוג, יקפיץ את המוניטין שלך לקהל גדול שאסור לך להחמיץ!
ועכשיו בהזדמנות, מבצע פסח 10% הנחה ברכישת מנוי שנתי!
לוח לימודים
מסלולי לימוד שאפשר לההצטרף
אליהם ממש עכשיו:
2.04
כ"ג אדר ב'
השקה חגיגית
חדש בפרוג
קורס חדשנות AI ובינה מלאכותית
14 שיעורים מפוצצים תוכן על כלי הAI השונים ליצירת תמונות וויז'ואל, עריכת וידאו ומושן, כתיבה ורעיונות, אפיון ועיצוב אתרים ועוד המון!
ההרשמה נפתחה!
20.03
י' אדר ב'
פתיחת מסלול
עיצוב ואדריכלות פנים
מלגות גבוהות!
26.03
טז' אדר ב'
פתיחת מסלול
מאסטר בשיווק דיגיטלי
מלגות גבוהות!
8.05
ל' ניסן
פתיחת מסלול
אוטומציות עסקיות, בוטים והטמעת מערכות מידע
מלגות גבוהות!
9.05
א' אייר
ירושלמי?
יש לנו מלגה מטורפת עבורך! קורס במימון כמעט מלא!!
אוטומציות עסקיות, בוטים והטמעת מערכות מידע
ההרשמה בעיצומה
28.05
כ' אייר
פתיחת מסלול מורחב:
פיתוח ובניית אתרים
מלגות גבוהות!
תהילים פרק קיט ק'
קמה קָרָאתִי בְכָל לֵב עֲנֵנִי יְהוָה חֻקֶּיךָ אֶצֹּרָה:קמו קְרָאתִיךָ הוֹשִׁיעֵנִי וְאֶשְׁמְרָה עֵדֹתֶיךָ:קמז קִדַּמְתִּי בַנֶּשֶׁף וָאֲשַׁוֵּעָה (לדבריך) לִדְבָרְךָ יִחָלְתִּי:קמח קִדְּמוּ עֵינַי אַשְׁמֻרוֹת לָשִׂיחַ בְּאִמְרָתֶךָ:קמט קוֹלִי שִׁמְעָה כְחַסְדֶּךָ יְהוָה כְּמִשְׁפָּטֶךָ חַיֵּנִי:קנ קָרְבוּ רֹדְפֵי זִמָּה מִתּוֹרָתְךָ רָחָקוּ:קנא קָרוֹב אַתָּה יְהוָה וְכָל מִצְוֹתֶיךָ אֱמֶת:קנב קֶדֶם יָדַעְתִּי מֵעֵדֹתֶיךָ כִּי לְעוֹלָם יְסַדְתָּם: