MINIMALIOS LENTOS PJAUSTYMO Į KVADRATUS KAINA

Išbandykite „GfG Practice“. Minimalios lentos pjaustymo į kvadratus kaina

Pateikta matmenų lenta n × m kurį reikia supjaustyti į n × m kvadratus. Pjovimo išilgai horizontalaus arba vertikalaus krašto kaina pateikiama dviem masyvais:

x[] : Pjovimo išlaidos išilgai vertikalių kraštų (pagal ilgį).
ir [] : Pjovimo išlaidos išilgai horizontalių kraštų (pločio atžvilgiu).

Raskite minimalias bendras išlaidas, kurių reikia norint optimaliai supjaustyti lentą į kvadratus.

Pavyzdžiai:

Įvestis: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Išvestis: 42
Paaiškinimas:

Iš pradžių ne. horizontalių segmentų = 1 ir ne. vertikalių segmentų = 1.
Optimalus pjaustymo į kvadratą būdas yra:
Pasirinkite 4 (iš x) -> vertikalus pjovimas Kaina = 4 × horizontalūs segmentai = 4
Dabar horizontalūs segmentai = 1 vertikalūs segmentai = 2.
Pasirinkite 4 (iš y) -> horizontalus pjūvis Kaina = 4 × vertikalūs segmentai = 8
Dabar horizontalūs segmentai = 2 vertikalūs segmentai = 2.
Pasirinkite 3 (iš x) -> vertikalus pjovimas Kaina = 3 × horizontalūs segmentai = 6
Dabar horizontalūs segmentai = 2 vertikalūs segmentai = 3.
Pasirinkite 2 (iš x) -> vertikalus pjovimas Kaina = 2 × horizontalūs segmentai = 4
Dabar horizontalūs segmentai = 2 vertikalūs segmentai = 4.
Pasirinkite 2 (iš y) -> horizontalus pjūvis Kaina = 2 × vertikalūs segmentai = 8
Dabar horizontalūs segmentai = 3 vertikalūs segmentai = 4.
Pasirinkite 1 (iš x) -> vertikalus pjovimas Kaina = 1 × horizontalūs segmentai = 3
Dabar horizontalūs segmentai = 3 vertikalūs segmentai = 5.
Pasirinkite 1 (iš x) -> vertikalus pjovimas Kaina = 1 × horizontalūs segmentai = 3
Dabar horizontalūs segmentai = 3 vertikalūs segmentai = 6.
Pasirinkite 1 (iš y) -> horizontalus pjūvis Kaina = 1 × vertikalūs segmentai = 6
Dabar horizontalūs segmentai = 4 vertikalūs segmentai = 6.
Taigi bendra kaina = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Įvestis: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Išvestis: 15
Paaiškinimas:
Iš pradžių ne. horizontalių segmentų = 1 ir ne. vertikalių segmentų = 1.
Optimalus pjaustymo į kvadratą būdas yra:
Pasirinkite 1 (iš y) -> horizontalus pjūvis Kaina = 1 × vertikalūs segmentai = 1
Dabar horizontalūs segmentai = 2 vertikalūs segmentai = 1.
Pasirinkite 1 (iš y) -> horizontalus pjūvis Kaina = 1 × vertikalūs segmentai = 1
Dabar horizontalūs segmentai = 3 vertikalūs segmentai = 1.
Pasirinkite 1 (iš y) -> horizontalus pjūvis Kaina = 1 × vertikalūs segmentai = 1
Dabar horizontalūs segmentai = 4 vertikalūs segmentai = 1.
Pasirinkite 1 (iš x) -> vertikalus pjovimas Kaina = 1 × horizontalūs segmentai = 4
Dabar horizontalūs segmentai = 4 vertikalūs segmentai = 2.
Pasirinkite 1 (iš x) -> vertikalus pjovimas Kaina = 1 × horizontalūs segmentai = 4
Dabar horizontalūs segmentai = 4 vertikalūs segmentai = 3.
Pasirinkite 1 (iš x) -> vertikalus pjovimas Kaina = 1 × horizontalūs segmentai = 4
Dabar horizontalūs segmentai = 4 vertikalūs segmentai = 4
Taigi bendra kaina = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Turinio lentelė

[Naivus požiūris] Išbandykite visas permutacijas – O((n+m)!×(n+m)) laikas ir O(n+m) erdvė
[Numatomas požiūris] naudojant godų techniką – O(n (log n)+m (log m)) laikas ir O(1) erdvė

[Naivus požiūris] Išbandykite visas permutacijas – O((n+m)!×(n+m)) laikas ir O(n+m) erdvė

Idėja yra sugeneruoti visas įmanomas duotų pjūvių permutacijas ir tada apskaičiuoti kiekvienos permutacijos kainą. Galiausiai grąžinkite minimalias išlaidas.

Pastaba: Šis metodas nėra įmanomas esant didesniems įėjimams, nes permutacijų skaičius didėja kaip (m+n-2)!.
Kiekvienai permutacijai turime apskaičiuoti kainą O(m+n) laiku. Taigi bendras laiko sudėtingumas tampa O((m+n−2)!×(m+n)).

[Numatomas požiūris] naudojant gobštą techniką – O(n (log n)+m (log m)) laikas ir O(1) erdvė

Idėja yra pirmiausia atlikti brangiausius pjūvius naudojant a godus požiūris . Pastebėta, kad kiekviename žingsnyje pasirinkus didžiausią išlaidų sumažinimą, būsimos išlaidos sumažinamos, nes vienu metu paveikiamos kelios dalys. Surūšiuojame vertikalią (x) ir horizontalią (y) išlaidas mažėjančia tvarka, tada pakartotinai pasirenkame didesnį, kad maksimaliai sutaupytume išlaidas. Likę pjūviai apdorojami atskirai, kad būtų užtikrintas optimalus visų dalių padalijimas.

Kas nutinka, kai padarome pjūvį?

Horizontalus pjūvis → pjaunate per plotį, todėl padidės horizontalių juostų skaičius (hCount++). Tačiau kaina padauginama iš vCount (vertikalių juostelių skaičiaus), nes horizontalus pjūvis turi praeiti per visus vertikalius segmentus.
Vertikalus pjūvis → pjaunate per aukštį, todėl vertikalių juostų skaičius padidės (vCount++). Tačiau kaina padauginama iš hCount (horizontalių juostelių skaičiaus), nes vertikalus pjūvis turi praeiti per visus horizontalius segmentus.

Problemos sprendimo žingsniai:

Rūšiuoti x ir y masyvus mažėjančia tvarka.
Naudokite du žymiklius, vieną x ir vieną y pradėdami nuo didžiausios vertės ir pereidami link mažesnių verčių.
Palaikykite hCount ir vCount jei norite stebėti, kiek segmentų paveikia kiekvienas iškirpimas, ir atitinkamai juos atnaujinti.
Kartokite, kol ir x, ir y yra neapdorotų pjūvių, visada rinkitės didesnę kainą, kad sumažintumėte bendras išlaidas.
Jei x likę iškirpimų, apdorokite juos naudodami hCount daugiklį; panašiai apdorokite likusius y pjūvius naudodami vCount.
Sukaupkite bendrą kainą kiekviename žingsnyje naudodami formulę: sumažinkite kainą * paveiktų dalių skaičius, užtikrindami minimalias išlaidas.

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