МИНИМАЛНА ЦЕНА ЗА НАРЯЗВАНЕ НА ДЪСКА НА КВАДРАТИ

Опитайте в GfG Practice Минимална цена за нарязване на дъска на квадрати

Дадена е дъска с размери n × m който трябва да бъде нарязан на n × m квадратчета. Цената за извършване на рязане по хоризонтален или вертикален ръб се предоставя в два масива:

х[] : Намаляване на разходите по вертикалните ръбове (по дължина).
и [] : Намаляване на разходите по хоризонталните ръбове (по ширина).

Намерете минималните общи разходи, необходими за оптимално нарязване на дъската на квадрати.

Примери:

вход: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 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 m = 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) пространство

Идеята е първо да направите най-скъпите разфасовки, като използвате a алчен подход . Наблюдението е, че избирането на най-голямото намаление на разходите на всяка стъпка намалява бъдещите разходи, като засяга множество части наведнъж. Сортираме разходите за вертикално (x) и хоризонтално (y) намаление в низходящ ред, след което итеративно избираме по-голямото, за да постигнем максимално спестяване на разходи. Останалите разфасовки се обработват отделно, за да се гарантира, че всички секции са разделени оптимално.

Какво се случва, когато направим разрез?

Хоризонтален разрез → режете по ширината, така че броят на хоризонталните ленти се увеличава (hCount++). Но цената се умножава по vCount (броя на вертикалните ивици), тъй като хоризонталният разрез трябва да премине през всички вертикални сегменти.
Вертикален разрез → режете напречно по височина, така че броят на вертикалните ленти се увеличава (vCount++). Но цената се умножава по hCount (броят хоризонтални ивици), тъй като вертикалният разрез трябва да премине през всички хоризонтални сегменти.

Стъпки за решаване на проблема:

Сортирайте както x, така и y масивите в низходящ ред.
Използвайте два указателя, един за x и един за y, започвайки от най-голямата стойност и преминавайки към по-малки стойности.
Поддържайте hCount и vCount за да проследите колко сегмента засяга всяко изрязване и да ги актуализирате съответно.
Повторете докато x и y имат необработени разфасовки, като винаги избирате по-голямата цена, за да минимизирате общите разходи.
Ако x има оставащи разрези, обработете ги с hCount множител; по подобен начин обработете останалите y разрези с 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  ));