MINIMÁLIS KÖLTSÉG EGY TÁBLA NÉGYZETEKRE VÁGÁSÁHOZ

Próbáld ki a GfG Practice-n Minimális költség egy tábla négyzetekre vágásához

Adott egy mérettábla n × m amit n × m-es négyzetekre kell vágni. A vízszintes vagy függőleges él mentén történő vágás költsége két tömbben található:

x[] : Vágási költségek a függőleges élek mentén (hosszonként).
és[] : Vágási költségek a vízszintes élek mentén (szélesség szerint).

Keresse meg azt a minimális összköltséget, amely a tábla optimális négyzetekre vágásához szükséges.

Példák:

Bemenet: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Kimenet: 42
Magyarázat:

Kezdetben nem. vízszintes szegmensek száma = 1 és nem. függőleges szegmensek száma = 1.
A négyzetre vágás optimális módja:
Válasszon 4-et (xből) -> függőleges vágás Költség = 4 × vízszintes szegmens = 4
Most vízszintes szegmensek = 1 függőleges szegmens = 2.
Válasszon 4-et (y-ból) -> vízszintes vágás Költség = 4 × függőleges szegmensek = 8
Most vízszintes szegmensek = 2 függőleges szegmens = 2.
Válasszon 3-at (xből) -> függőleges vágás Költség = 3 × vízszintes szegmens = 6
Most vízszintes szegmensek = 2 függőleges szegmens = 3.
Válasszon 2-t (xből) -> függőleges vágás Költség = 2 × vízszintes szegmensek = 4
Most vízszintes szegmensek = 2 függőleges szegmens = 4.
Válasszon 2-t (y-ból) -> vízszintes vágás Költség = 2 × függőleges szegmensek = 8
Most vízszintes szegmensek = 3 függőleges szegmens = 4.
Válasszon 1-et (xből) -> függőleges vágás Költség = 1 × vízszintes szegmensek = 3
Most vízszintes szegmensek = 3 függőleges szegmens = 5.
Válasszon 1-et (xből) -> függőleges vágás Költség = 1 × vízszintes szegmensek = 3
Most vízszintes szegmensek = 3 függőleges szegmens = 6.
Válasszon 1-et (y-ból) -> vízszintes vágás Költség = 1 × függőleges szegmensek = 6
Most vízszintes szegmensek = 4 függőleges szegmens = 6.
Tehát a teljes költség = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Bemenet: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Kimenet: 15
Magyarázat:
Kezdetben nem. vízszintes szegmensek száma = 1 és nem. függőleges szegmensek száma = 1.
A négyzetre vágás optimális módja:
Válasszon 1-et (y-ból) -> vízszintes vágás Költség = 1 × függőleges szegmensek = 1
Most vízszintes szegmensek = 2 függőleges szegmens = 1.
Válasszon 1-et (y-ból) -> vízszintes vágás Költség = 1 × függőleges szegmensek = 1
Most vízszintes szegmensek = 3 függőleges szegmens = 1.
Válasszon 1-et (y-ból) -> vízszintes vágás Költség = 1 × függőleges szegmensek = 1
Most vízszintes szegmensek = 4 függőleges szegmens = 1.
Válasszon 1-et (xből) -> függőleges vágás Költség = 1 × vízszintes szegmensek = 4
Most vízszintes szegmensek = 4 függőleges szegmens = 2.
Válasszon 1-et (xből) -> függőleges vágás Költség = 1 × vízszintes szegmensek = 4
Most vízszintes szegmensek = 4 függőleges szegmens = 3.
Válasszon 1-et (xből) -> függőleges vágás Költség = 1 × vízszintes szegmensek = 4
Most vízszintes szegmensek = 4 függőleges szegmens = 4
Tehát a teljes költség = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Tartalomjegyzék

[Naiv megközelítés] Próbáljon ki minden permutációt – O((n+m)!×(n+m)) idő és O(n+m) tér
[Várható megközelítés] Mohó technikával – O(n (log n)+m (log m)) idő és O(1) tér

[Naiv megközelítés] Próbáljon ki minden permutációt – O((n+m)!×(n+m)) idő és O(n+m) tér

Az ötlet az, hogy az adott vágások összes lehetséges permutációját generáljuk, majd kiszámítjuk az egyes permutációk költségét. Végül adja vissza köztük a minimális költséget.

Jegyzet: Ez a megközelítés nagyobb bemeneteknél nem kivitelezhető, mert a permutációk száma faktorálisan nő (m+n-2)!.
Minden permutációhoz ki kell számítanunk a költséget O(m+n) időben. Így a teljes időbonyolultság O((m+n−2)!×(m+n)).

[Várható megközelítés] Mohó technikával – O(n (log n)+m (log m)) idő és O(1) tér

Az ötlet az, hogy a legdrágább vágásokat először a mohó megközelítés . A megfigyelés szerint a legmagasabb költségcsökkentés kiválasztása minden lépésnél csökkenti a jövőbeli költségeket, mivel több darabot egyszerre érint. A függőleges (x) és vízszintes (y) költségcsökkentést csökkenő sorrendbe rendezzük, majd iteratív módon kiválasztjuk a nagyobbat, hogy maximalizáljuk a költségmegtakarítást. A fennmaradó vágásokat külön dolgozzák fel, hogy biztosítsák az összes szakasz optimális felosztását.

Mi történik, ha vágunk?

Vízszintes vágás → szélességben vág, így nő a vízszintes csíkok száma (hCount++). De a költséget megszorozzák a vCount-al (a függőleges csíkok számával), mivel a vízszintes vágásnak át kell haladnia az összes függőleges szegmensen.
Függőleges vágás → átvágja a magasságot, így a függőleges csíkok száma nő (vCount++). De a költséget megszorozzák a hCount-al (a vízszintes csíkok számával), mivel a függőleges vágásnak át kell haladnia az összes vízszintes szegmensen.

A probléma megoldásának lépései:

Rendezze az x és y tömböket csökkenő sorrendbe.
Használjon két mutatót egy x-hez, egyet pedig y-hoz a legnagyobb értéktől kezdve és a kisebb értékek felé haladva.
A hCount és a vCount karbantartásával nyomon követheti, hogy az egyes vágások hány szegmenst érintenek, és ennek megfelelően frissíti őket.
Iteráljon, miközben az x-nek és az y-nak is vannak feldolgozatlan vágásai, mindig a nagyobb költséget választva az általános költségek minimalizálása érdekében.
Ha x-nek van még darabja, dolgozza fel azokat a hCount szorzóval; hasonlóan dolgozza fel a fennmaradó y vágásokat a vCount segítségével.
Minden lépésnél felhalmozhatja a teljes költséget a következő képlet segítségével: költségcsökkentés * az érintett darabok száma minimális költség biztosítása érdekében.

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