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

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

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

Примери: 

вход: 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.
• Натрупайте обща цена на всяка стъпка, като използвате формулата: намалете разходите * брой засегнати части, осигурявайки минимални разходи.

#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; } 

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 = 4m = 6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  System.out.println(minCost(n m x y));  } } 

def minCost(nm 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__': nm = 4 6 x = [2 1 3 1 4] y = [4 1 2] print(minCost(nmx 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=4m=6;  int[] x = {2 1 3 1 4};  int[] y = {4 1 2};  Console.WriteLine(minCost(nm x y));  } } 

function minCost( nm 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 = 4m = 6; let x = [2 1 3 1 4]; let y = [4 1 2]; console.log(minCost(nm x y)); 

42