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 gobštą 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ūšiuokite x ir y masyvus mažėjimo 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.

#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