MINIMÁLNÍ NÁKLADY NA ROZŘEZÁNÍ DESKY NA ČTVERCE

Zkuste to na GfG Practice Minimální náklady na rozřezání desky na čtverce

Vzhledem k desce rozměrů n × m které je třeba rozřezat na n × m čtverců. Náklady na provedení řezu podél vodorovného nebo svislého okraje jsou poskytovány ve dvou polích:

x[] : Snížení nákladů podél svislých hran (podélně).
a[] : Snížení nákladů podél vodorovných okrajů (na šířku).

Najděte minimální celkové náklady potřebné k optimálnímu rozřezání desky na čtverce.

Příklady:

Vstup: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
výstup: 42
Vysvětlení:

Zpočátku ne. horizontálních segmentů = 1 & no. svislých segmentů = 1.
Optimální způsob řezání na čtverec je:
Vyberte 4 (z x) -> vertikální řez Cena = 4 × horizontální segmenty = 4
Nyní horizontální segmenty = 1 vertikální segmenty = 2.
Vyberte 4 (z y) -> horizontální řez Cena = 4 × svislé segmenty = 8
Nyní horizontální segmenty = 2 vertikální segmenty = 2.
Vyberte 3 (z x) -> vertikální řez Cena = 3 × horizontální segmenty = 6
Nyní horizontální segmenty = 2 vertikální segmenty = 3.
Vyberte 2 (z x) -> vertikální řez Cena = 2 × horizontální segmenty = 4
Nyní horizontální segmenty = 2 vertikální segmenty = 4.
Vyberte 2 (z y) -> horizontální řez Cena = 2 × svislé segmenty = 8
Nyní horizontální segmenty = 3 vertikální segmenty = 4.
Vyberte 1 (z x) -> vertikální řez Cena = 1 × horizontální segmenty = 3
Nyní horizontální segmenty = 3 vertikální segmenty = 5.
Vyberte 1 (z x) -> vertikální řez Cena = 1 × horizontální segmenty = 3
Nyní horizontální segmenty = 3 vertikální segmenty = 6.
Vyberte 1 (z y) -> horizontální řez Cena = 1 × svislé segmenty = 6
Nyní horizontální segmenty = 4 vertikální segmenty = 6.
Takže celkové náklady = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Vstup: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
výstup: 15
Vysvětlení:
Zpočátku ne. horizontálních segmentů = 1 & no. svislých segmentů = 1.
Optimální způsob řezání na čtverec je:
Vyberte 1 (z y) -> horizontální řez Cena = 1 × svislé segmenty = 1
Nyní horizontální segmenty = 2 vertikální segmenty = 1.
Vyberte 1 (z y) -> horizontální řez Cena = 1 × svislé segmenty = 1
Nyní horizontální segmenty = 3 vertikální segmenty = 1.
Vyberte 1 (z y) -> horizontální řez Cena = 1 × svislé segmenty = 1
Nyní horizontální segmenty = 4 vertikální segmenty = 1.
Vyberte 1 (z x) -> vertikální řez Cena = 1 × horizontální segmenty = 4
Nyní horizontální segmenty = 4 vertikální segmenty = 2.
Vyberte 1 (z x) -> vertikální řez Cena = 1 × horizontální segmenty = 4
Nyní horizontální segmenty = 4 vertikální segmenty = 3.
Vyberte 1 (z x) -> vertikální řez Cena = 1 × horizontální segmenty = 4
Nyní horizontální segmenty = 4 vertikální segmenty = 4
Takže celkové náklady = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Obsah

[Naivní přístup] Vyzkoušejte všechny permutace – O((n+m)!×(n+m)) Čas a O(n+m) Prostor
[Očekávaný přístup] Použití chamtivé techniky - O( n (log n)+m (log m)) Čas a O(1) Prostor

[Naivní přístup] Vyzkoušejte všechny permutace – O((n+m)!×(n+m)) Čas a O(n+m) Prostor

Cílem je vygenerovat všechny možné permutace daných řezů a poté vypočítat náklady na každou permutaci. Nakonec mezi ně vraťte minimální náklady.

Poznámka: Tento přístup není proveditelný pro větší vstupy, protože počet permutací roste faktoriálně jako (m+n-2)!.
Pro každou permutaci musíme vypočítat náklady v O(m+n) čase. Celková časová složitost se tak stává O((m+n−2)!×(m+n)).

[Očekávaný přístup] Použití chamtivé techniky - O( n (log n)+m (log m)) Čas a O(1) Prostor

Cílem je provést nejdražší řezy nejprve pomocí a zištný přístup . Pozorování je, že výběr nejvyššího snížení nákladů v každém kroku snižuje budoucí náklady ovlivněním více kusů najednou. Seřadíme vertikální (x) a horizontální (y) snížené náklady v sestupném pořadí a poté iterativně vybíráme větší, abychom maximalizovali úspory nákladů. Zbývající řezy jsou zpracovávány samostatně, aby bylo zajištěno optimální rozdělení všech částí.

Co se stane, když uděláme řez?

Horizontální řez → řežete po šířce, takže se zvyšuje počet vodorovných pruhů (hCount++). Náklady se však vynásobí vCount (počet svislých pruhů), protože horizontální řez musí procházet všemi vertikálními segmenty.
Vertikální řez → řežete přes výšku, takže se zvyšuje počet svislých pruhů (vCount++). Náklady se však násobí hCount (počet vodorovných pásů), protože vertikální řez musí procházet všemi horizontálními segmenty.

Kroky k vyřešení problému:

Seřaďte pole x a y v sestupném pořadí.
Použijte dva ukazatele, jeden pro x a jeden pro y, počínaje nejvyšší hodnotou a postupujte směrem k menším hodnotám.
Udržujte hodnoty hCount a vCount, abyste mohli sledovat, kolik segmentů každý řez ovlivňuje, a podle toho je aktualizujte.
Opakujte, zatímco x a y mají nezpracované škrty, vždy vyberte vyšší náklady, abyste minimalizovali celkové náklady.
Pokud x má zbývající řezy, zpracujte je pomocí násobiče hCount; podobně zpracujte zbývající y řezy pomocí vCount.
Shromážděte celkové náklady v každém kroku pomocí vzorce: snížit náklady * počet dotčených kusů zajišťující minimální náklady.

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  ));