עלות מינימלית לחיתוך לוח לריבועים

נסה את זה ב-GfG Practice עלות מינימלית לחיתוך לוח לריבועים

נתון לוח מידות n × מ' שצריך לחתוך ל-n × מ' ריבועים. העלות של ביצוע חיתוך לאורך קצה אופקי או אנכי מסופקת בשני מערכים:

x[] : חיתוך עלויות לאורך הקצוות האנכיים (לאורך).
ו[] : חיתוך עלויות לאורך הקצוות האופקיים (לרוחב).

מצא את העלות הכוללת המינימלית הנדרשת כדי לחתוך את הלוח לריבועים בצורה מיטבית.

דוגמאות:

קֶלֶט: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 מ' = 6
תְפוּקָה: 42
הֶסבֵּר:

בתחילה לא. של מקטעים אופקיים = 1 & לא. של מקטעים אנכיים = 1.
הדרך האופטימלית לחתוך לריבוע היא:
בחר 4 (מ-x) -> חיתוך אנכי עלות = 4 × מקטעים אופקיים = 4
כעת מקטעים אופקיים = 1 מקטע אנכי = 2.
בחר 4 (מ-y) -> חיתוך אופקי עלות = 4 × מקטעים אנכיים = 8
כעת קטעים אופקיים = 2 קטעים אנכיים = 2.
בחר 3 (מ-x) -> חיתוך אנכי עלות = 3 × מקטעים אופקיים = 6
כעת מקטעים אופקיים = 2 מקטעים אנכיים = 3.
בחר 2 (מ-x) -> חיתוך אנכי עלות = 2 × מקטעים אופקיים = 4
כעת קטעים אופקיים = 2 קטעים אנכיים = 4.
בחר 2 (מ-y) -> חיתוך אופקי עלות = 2 × מקטעים אנכיים = 8
כעת מקטעים אופקיים = 3 מקטעים אנכיים = 4.
בחר 1 (מ-x) -> חיתוך אנכי עלות = 1 × מקטעים אופקיים = 3
כעת מקטעים אופקיים = 3 מקטעים אנכיים = 5.
בחר 1 (מ-x) -> חיתוך אנכי עלות = 1 × מקטעים אופקיים = 3
כעת מקטעים אופקיים = 3 מקטעים אנכיים = 6.
בחר 1 (מ-y) -> חיתוך אופקי עלות = 1 × מקטעים אנכיים = 6
כעת מקטעים אופקיים = 4 מקטעים אנכיים = 6.
אז העלות הכוללת = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

קֶלֶט: x[] = [1 1 1] y[] = [1 1 1] n = 4 מ' = 4
תְפוּקָה: 15
הֶסבֵּר:
בתחילה לא. של מקטעים אופקיים = 1 & לא. של מקטעים אנכיים = 1.
הדרך האופטימלית לחתוך לריבוע היא:
בחר 1 (מ-y) -> חיתוך אופקי עלות = 1 × מקטעים אנכיים = 1
כעת מקטעים אופקיים = 2 מקטעים אנכיים = 1.
בחר 1 (מ-y) -> חיתוך אופקי עלות = 1 × מקטעים אנכיים = 1
כעת מקטעים אופקיים = 3 מקטעים אנכיים = 1.
בחר 1 (מ-y) -> חיתוך אופקי עלות = 1 × מקטעים אנכיים = 1
כעת מקטעים אופקיים = 4 מקטעים אנכיים = 1.
בחר 1 (מ-x) -> חיתוך אנכי עלות = 1 × מקטעים אופקיים = 4
כעת מקטעים אופקיים = 4 מקטעים אנכיים = 2.
בחר 1 (מ-x) -> חיתוך אנכי עלות = 1 × מקטעים אופקיים = 4
כעת מקטעים אופקיים = 4 מקטעים אנכיים = 3.
בחר 1 (מ-x) -> חיתוך אנכי עלות = 1 × מקטעים אופקיים = 4
כעת מקטעים אופקיים = 4 מקטעים אנכיים = 4
אז העלות הכוללת = 1 + 1 + 1 + 4 + 4 + 4 = 15.

תוכן עניינים

[גישה נאיבית] נסה את כל התמורות - O((n+m)!×(n+m)) זמן ו-O(n+m) מרחב
[גישה צפויה] שימוש בטכניקה חמדנית - O( n (log n)+m (log m)) זמן ו-O(1) מרחב

[גישה נאיבית] נסה את כל התמורות - O((n+m)!×(n+m)) זמן ו-O(n+m) מרחב

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

פֶּתֶק: גישה זו אינה ריאלית עבור תשומות גדולות יותר מכיוון שמספר התמורות גדל באופן פקטוריאלי כ- (m+n-2)!.
עבור כל תמורה עלינו לחשב את העלות בזמן O(m+n). מכאן שמורכבות הזמן הכוללת הופכת ל-O((m+n−2)!×(m+n)).

[גישה צפויה] שימוש בטכניקה חמדנית - O( n (log n)+m (log m)) זמן ו-O(1) מרחב

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

מה קורה כשאנחנו עושים חתך?

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

שלבים לפתרון הבעיה:

מיין את מערכי x וגם y בסדר יורד.
השתמש בשני מצביעים, אחד עבור x ואחד עבור y מתחיל מהערך הגדול ביותר ומתקדם לערכים קטנים יותר.
שמרו על hCount ו VCount כדי לעקוב אחר כמה פלחים כל חתך משפיע ולעדכן אותם בהתאם.
חזור על בזמן שגם ל-x וגם ל-y יש קיצוצים לא מעובדים, תמיד בוחרים בעלות הגבוהה יותר כדי למזער את ההוצאות הכוללות.
אם ל-x יש חיתוכים שנותרו לעבד אותם עם מכפיל hCount; באופן דומה מעבדים את החתכים הנותרים עם vCount.
צבור עלות כוללת בכל שלב באמצעות הנוסחה: קצץ בעלות * מספר החלקים המושפעים ומבטיח עלות מינימלית.

C++

    #include       #include      #include       using     namespace     std  ;   int     minCost  (  int     n       int     m           vector   <  int  >&     x       vector   <  int  >&     y  )     {          // Sort the cutting costs in ascending order      sort  (  x  .  begin  ()     x  .  end  ());      sort  (  y  .  begin  ()     y  .  end  ());         int     hCount     =     1       vCount     =     1  ;         int     i     =     x  .  size  ()     -     1       j     =     y  .  size  ()     -     1  ;         int     totalCost     =     0  ;      while     (  i     >=     0     &&     j     >=     0  )     {          // Choose the larger cost cut to       // minimize future costs      if     (  x  [  i  ]     >=     y  [  j  ])     {      totalCost     +=     x  [  i  ]     *     hCount  ;         vCount  ++  ;      i  --  ;      }         else     {      totalCost     +=     y  [  j  ]     *     vCount  ;         hCount  ++  ;      j  --  ;      }      }      // Process remaining vertical cuts      while     (  i     >=     0  )     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }      // Process remaining horizontal cuts      while     (  j     >=     0  )     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      return     totalCost  ;   }   int     main  ()     {          int     n     =     4       m     =     6  ;      vector   <  int  >     x     =     {  2       1       3       1       4  };      vector   <  int  >     y     =     {  4       1       2  };      cout      < <     minCost  (  n       m       x       y  )      < <     endl  ;      return     0  ;   }

Java

    import     java.util.Arrays  ;   class   GfG     {          static     int     minCost  (  int     n       int     m           int  []     x       int  []     y  )     {          // Sort the cutting costs in ascending order      Arrays  .  sort  (  x  );      Arrays  .  sort  (  y  );         int     hCount     =     1       vCount     =     1  ;         int     i     =     x  .  length     -     1       j     =     y  .  length     -     1  ;         int     totalCost     =     0  ;      while     (  i     >=     0     &&     j     >=     0  )     {          // Choose the larger cost cut to       // minimize future costs      if     (  x  [  i  ]     >=     y  [  j  ]  )     {      totalCost     +=     x  [  i  ]     *     hCount  ;         vCount  ++  ;      i  --  ;      }         else     {      totalCost     +=     y  [  j  ]     *     vCount  ;         hCount  ++  ;      j  --  ;      }      }      // Process remaining vertical cuts      while     (  i     >=     0  )     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }      // Process remaining horizontal cuts      while     (  j     >=     0  )     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      return     totalCost  ;      }      public     static     void     main  (  String  []     args  )     {          int     n     =     4    m     =     6  ;      int  []     x     =     {  2       1       3       1       4  };      int  []     y     =     {  4       1       2  };      System  .  out  .  println  (  minCost  (  n       m       x       y  ));      }   }

Python

    def   minCost  (  n    m     x     y  ):   # Sort the cutting costs in ascending order   x  .  sort  ()   y  .  sort  ()   hCount     vCount   =   1     1   i     j   =   len  (  x  )   -   1     len  (  y  )   -   1   totalCost   =   0   while   i   >=   0   and   j   >=   0  :   # Choose the larger cost cut to    # minimize future costs   if   x  [  i  ]   >=   y  [  j  ]:   totalCost   +=   x  [  i  ]   *   hCount   vCount   +=   1   i   -=   1   else  :   totalCost   +=   y  [  j  ]   *   vCount   hCount   +=   1   j   -=   1   # Process remaining vertical cuts   while   i   >=   0  :   totalCost   +=   x  [  i  ]   *   hCount   vCount   +=   1   i   -=   1   # Process remaining horizontal cuts   while   j   >=   0  :   totalCost   +=   y  [  j  ]   *   vCount   hCount   +=   1   j   -=   1   return   totalCost   if   __name__   ==   '__main__'  :   n    m   =   4     6   x   =   [  2     1     3     1     4  ]   y   =   [  4     1     2  ]   print  (  minCost  (  n    m    x     y  ))

    using     System  ;   class     GfG     {      public     static     int     minCost  (  int     n       int     m           int  []     x       int  []     y  )     {          // Sort the cutting costs in ascending order      Array  .  Sort  (  x  );      Array  .  Sort  (  y  );      int     hCount     =     1       vCount     =     1  ;      int     i     =     x  .  Length     -     1       j     =     y  .  Length     -     1  ;      int     totalCost     =     0  ;      // Process the cuts in greedy manner      while     (  i     >=     0     &&     j     >=     0  )     {          // Choose the larger cost cut to       // minimize future costs      if     (  x  [  i  ]     >=     y  [  j  ])     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }      else     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      }      // Process remaining vertical cuts      while     (  i     >=     0  )     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }      // Process remaining horizontal cuts      while     (  j     >=     0  )     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      return     totalCost  ;      }          public     static     void     Main  ()     {          int     n  =  4    m  =  6  ;      int  []     x     =     {  2       1       3       1       4  };      int  []     y     =     {  4       1       2  };      Console  .  WriteLine  (  minCost  (  n    m       x       y  ));      }   }

JavaScript

    function     minCost  (     n    m       x       y  )     {          // Sort the cutting costs in ascending order      x  .  sort  ((  a       b  )     =>     a     -     b  );      y  .  sort  ((  a       b  )     =>     a     -     b  );      let     hCount     =     1       vCount     =     1  ;      let     i     =     x  .  length     -     1       j     =     y  .  length     -     1  ;      let     totalCost     =     0  ;      while     (  i     >=     0     &&     j     >=     0  )     {          // Choose the larger cost cut to       // minimize future costs      if     (  x  [  i  ]     >=     y  [  j  ])     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }         else     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      }      // Process remaining vertical cuts      while     (  i     >=     0  )     {      totalCost     +=     x  [  i  ]     *     hCount  ;      vCount  ++  ;      i  --  ;      }      // Process remaining horizontal cuts      while     (  j     >=     0  )     {      totalCost     +=     y  [  j  ]     *     vCount  ;      hCount  ++  ;      j  --  ;      }      return     totalCost  ;   }   // Driver Code   let     n     =     4    m     =     6  ;   let     x     =     [  2       1       3       1       4  ];   let     y     =     [  4       1       2  ];   console  .  log  (  minCost  (  n    m       x       y  ));