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.

#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