Gitt et bord av dimensjoner n × m som må kuttes i n × m firkanter. Kostnaden for å lage et kutt langs en horisontal eller vertikal kant er gitt i to matriser:

• x[] : Kuttekostnader langs de vertikale kantene (lengdevis).
• og[] : Kutte kostnader langs de horisontale kantene (breddevis).

Finn minimum totalkostnad som kreves for å kutte brettet i firkanter optimalt.

Eksempler: 

Inndata: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Produksjon: 42
Forklaring:

I utgangspunktet nei. av horisontale segmenter = 1 & nr. av vertikale segmenter = 1.
Optimal måte å kutte i firkanter er:
Velg 4 (fra x) -> vertikalt kutt Kostnad = 4 × horisontale segmenter = 4
 Nå horisontale segmenter = 1 vertikale segmenter = 2.
Velg 4 (fra y) -> horisontalt kutt Kostnad = 4 × vertikale segmenter = 8
 Nå horisontale segmenter = 2 vertikale segmenter = 2.
Velg 3 (fra x) -> vertikalt kutt Kostnad = 3 × horisontale segmenter = 6
 Nå horisontale segmenter = 2 vertikale segmenter = 3.
Velg 2 (fra x) -> vertikalt kutt Kostnad = 2 × horisontale segmenter = 4
 Nå horisontale segmenter = 2 vertikale segmenter = 4.
Velg 2 (fra y) -> horisontalt kutt Kostnad = 2 × vertikale segmenter = 8
 Nå horisontale segmenter = 3 vertikale segmenter = 4.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 3
Nå horisontale segmenter = 3 vertikale segmenter = 5.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 3
Nå horisontale segmenter = 3 vertikale segmenter = 6.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 6
Nå horisontale segmenter = 4 vertikale segmenter = 6.
Så den totale kostnaden = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Inndata: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Produksjon: 15
Forklaring:
I utgangspunktet nei. av horisontale segmenter = 1 & nr. av vertikale segmenter = 1.
Optimal måte å kutte i firkanter er:
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 2 vertikale segmenter = 1.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 3 vertikale segmenter = 1.
Velg 1 (fra y) -> horisontalt kutt Kostnad = 1 × vertikale segmenter = 1
Nå horisontale segmenter = 4 vertikale segmenter = 1.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 2.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 3.
Velg 1 (fra x) -> vertikalt kutt Kostnad = 1 × horisontale segmenter = 4
Nå horisontale segmenter = 4 vertikale segmenter = 4
Så den totale kostnaden = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Innholdsfortegnelse

• [Naiv tilnærming] Prøv alle permutasjoner - O((n+m)!×(n+m)) Tid og O(n+m) Mellomrom
• [Forventet tilnærming] Bruke grådig teknikk - O( n (log n)+m (log m)) Tid og O(1) Mellomrom

[Naiv tilnærming] Prøv alle permutasjoner - O((n+m)!×(n+m)) Tid og O(n+m) Mellomrom

Tanken er å generere alle mulige permutasjoner av de gitte kuttene og deretter beregne kostnadene for hver permutasjon. Til slutt returner minimumskostnaden blant dem.

Note: Denne tilnærmingen er ikke mulig for større innganger fordi antall permutasjoner vokser faktorielt som (m+n-2)!.
For hver permutasjon må vi beregne kostnaden i O(m+n) tid. Derfor blir den totale tidskompleksiteten O((m+n−2)!×(m+n)).

[Forventet tilnærming] Bruke grådig teknikk - O( n (log n)+m (log m)) Tid og O(1) Mellomrom

Tanken er å gjøre de dyreste kuttene først ved å bruke en grådig tilnærming . Observasjonen er at å velge det høyeste kostnadskuttet ved hvert trinn reduserer fremtidige kostnader ved å påvirke flere deler samtidig. Vi sorterer de vertikale (x) og horisontale (y) kuttkostnadene i synkende rekkefølge og velger iterativt den største for å maksimere kostnadsbesparelser. De resterende kuttene behandles separat for å sikre at alle seksjoner deles optimalt.

Hva skjer når vi gjør et kutt?

• Horisontalt kutt → du kutter på tvers av bredden slik at antallet horisontale strimler øker (hCount++). Men kostnaden multipliseres med vCount (antall vertikale strimler) fordi det horisontale kuttet må passere gjennom alle vertikale segmenter.
• Vertikalt kutt → du kutter på tvers av høyden slik at antallet vertikale strimler øker (vCount++). Men kostnaden multipliseres med hCount (antall horisontale strimler) fordi det vertikale kuttet må passere gjennom alle horisontale segmenter.

Trinn for å løse problemet:

• Sorter både x og y matriser i synkende rekkefølge.
• Bruk to pekere, én for x og én for y, start fra den største verdien og beveger seg mot mindre verdier.
• Oppretthold hCount og vCount for å spore hvor mange segmenter hvert kutt påvirker, og oppdater dem deretter.
• Gjenta mens både x og y har ubehandlede kutt, og velg alltid de høyere kostnadene for å minimere de totale utgiftene.
• Hvis x har gjenværende kutt, behandle dem med hCount multiplikator; behandle gjenværende y-kutt med vCount.
• Akkumuler totalkostnad ved hvert trinn ved å bruke formelen: kutt kostnad * antall berørte deler for å sikre minimal kostnad.

#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