תכנון דינאמי - בעיית המטבעות

[niro2003]

תכנון דינאמי - בעיית המטבעות

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

 

[vinney]

לא אוהב את השורה האחרונה

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

 

[niro2003]

מה זה פה, בלוג?

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

 

[vinney]

לא לא, זאת לא השאלה עצמה

זאת גרסה יותר קלה שלה. אם אני הבנתי את השאלה, זאת אומרת

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

אני מניח שמושג "רקורסיה" לא זר לך, בסופו של דבר זה מסתכם בספירה רקורסיבית של מסלולים בגרף.

 

[vinney]

(וההשתתפות באמת קצת דלילה...)

 

[niro2003]

מספר המטבעות הוא אינסופי

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

 

[טיורינג]

backtracking

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

 

[niro2003]

לא כ"כ הבנתי

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

 

[The Albatross]

מה זה תכנון דינאמי, אגב?

 

[vinney]

המם...

פה

 

[The Albatross]

זה נחמד מאוד, האמת.

איפה אפשר לקרוא על זה עוד?

 

[vinney]

המם...

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

 

[ron369]

לא שניים?

הרי חמדנות זה סוג של תכנות דינאמי - בערך...