Question

dynamic_programming

נתונה קבוצה של nn תיבות שכל אחת מהן מאופיינת על ידי גובה, אורך ורוחב. כאן, הסדר שבו נתונים מימדיה של תיבה אינו חשוב; לכן, תיבה שמימדיה 1×2×31 \times 2 \times 3 זהה לזו שמימדיה 2×1×32 \times 1 \times 3. ניתן להכניס תיבה AA לתוך תיבה BB אם ורק אם ניתן לסובב את AA כך שכל שלושת מימדיה יהיו קטנים ממש מאלו של BB. אין להכניס שתי תיבות (או יותר) זו ליד זו לתוך תיבה אחרת, אם אם הדבר אפשרי מבחינת מידות התיבות.

קבוצה טלסקופית היא קבוצה של תיבות המוכנסות זו בזו.

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

1

Answers

נגדיר גרף מכוון שבו כל צומת מתאים לתיבה. קשת uvuv קיימת בגרף אמ"מ התיבה שמתאימה ל-uu יכולה להיכנס לתיבה שמתאימה ל-vv.

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

אלגוריתם: מצא מסלול ארוך ביותר בגרף הנ"ל.

נכונות: נובעת מהדיון למעלה.

סיבוכיות: ניתן לעשות זאת בזמן לינארי על ידי תכנון דינמי.

1
Feedback