Annettu laudan mitat n × m joka on leikattava n × m neliöiksi. Leikkauksen tekeminen vaaka- tai pystyreunaa pitkin on kahdessa taulukossa:

• x[] : Leikkauskustannukset pystyreunoja pitkin (pituussuunnassa).
• ja[] : Leikkauskustannukset vaakasuorista reunoista (leveyssuunnassa).

Etsi vähimmäiskokonaiskustannukset, jotka vaaditaan levyn leikkaamiseen neliöiksi optimaalisesti.

Esimerkkejä: 

Syöte: x[] = [2 1 3 1 4] y[] = [4 1 2] n = 4 m = 6
Lähtö: 42
Selitys:

Aluksi ei. vaakasuorista segmenteistä = 1 & ei. pystysegmenttien määrä = 1.
Optimaalinen tapa leikata neliöiksi on:
Valitse 4 (x:stä) -> pystyleikkaus Hinta = 4 × vaakasegmentit = 4
 Nyt vaakasuuntaiset segmentit = 1 pystysegmentti = 2.
Valitse 4 (y:stä) -> vaakasuora leikkaus Hinta = 4 × pystysegmentit = 8
 Nyt vaakasuuntaiset segmentit = 2 pystysegmenttiä = 2.
Valitse 3 (x:stä) -> pystyleikkaus Kustannukset = 3 × vaakasuuntaiset segmentit = 6
 Nyt vaakasuuntaiset segmentit = 2 pystysegmenttiä = 3.
Valitse 2 (x:stä) -> pystyleikkaus Kustannukset = 2 × vaakasuuntaiset segmentit = 4
 Nyt vaakasuuntaiset segmentit = 2 pystysegmenttiä = 4.
Valitse 2 (yltä) -> vaakasuora leikkaus Hinta = 2 × pystysegmentit = 8
 Nyt vaakasuuntaiset segmentit = 3 pystysegmenttiä = 4.
Valitse 1 (x:stä) -> pystyleikkaus Kustannukset = 1 × vaakasegmentit = 3
Nyt vaakasuuntaiset segmentit = 3 pystysegmenttiä = 5.
Valitse 1 (x:stä) -> pystyleikkaus Kustannukset = 1 × vaakasegmentit = 3
Nyt vaakasuuntaiset segmentit = 3 pystysegmenttiä = 6.
Valitse 1 (yltä) -> vaakasuora leikkaus Hinta = 1 × pystysegmentit = 6
Nyt vaakasuuntaiset segmentit = 4 pystysegmenttiä = 6.
Joten kokonaiskustannukset = 4 + 8 + 6 + 4 + 8 + 3 + 3 + 6 = 42.

Syöte: x[] = [1 1 1] y[] = [1 1 1] n = 4 m = 4
Lähtö: 15
Selitys:
Aluksi ei. vaakasuorista segmenteistä = 1 & ei. pystysegmenttien määrä = 1.
Optimaalinen tapa leikata neliöiksi on:
Valitse 1 (yltä) -> vaakasuora leikkaus Hinta = 1 × pystysegmentit = 1
Nyt vaakasuuntaiset segmentit = 2 pystysegmenttiä = 1.
Valitse 1 (yltä) -> vaakasuora leikkaus Hinta = 1 × pystysegmentit = 1
Nyt vaakasuuntaiset segmentit = 3 pystysegmenttiä = 1.
Valitse 1 (yltä) -> vaakasuora leikkaus Hinta = 1 × pystysegmentit = 1
Nyt vaakasuuntaiset segmentit = 4 pystysegmenttiä = 1.
Valitse 1 (x:stä) -> pystyleikkaus Hinta = 1 × vaakasegmentit = 4
Nyt vaakasuuntaiset segmentit = 4 pystysegmenttiä = 2.
Valitse 1 (x:stä) -> pystyleikkaus Hinta = 1 × vaakasegmentit = 4
Nyt vaakasuuntaiset segmentit = 4 pystysegmenttiä = 3.
Valitse 1 (x:stä) -> pystyleikkaus Hinta = 1 × vaakasegmentit = 4
Nyt vaakasuuntaiset segmentit = 4 pystysegmenttiä = 4
Joten kokonaiskustannukset = 1 + 1 + 1 + 4 + 4 + 4 = 15.

Sisällysluettelo

• [Naiivi lähestymistapa] Kokeile kaikkia permutaatioita - O((n+m)!×(n+m)) aika ja O(n+m) avaruus
• [Odotettu lähestymistapa] Ahneella tekniikalla - O(n (log n)+m (log m)) aika ja O(1)-avaruus

[Naiivi lähestymistapa] Kokeile kaikkia permutaatioita - O((n+m)!×(n+m)) aika ja O(n+m) avaruus

Ajatuksena on luoda kaikki mahdolliset permutaatiot annetuille leikkauksille ja sitten laskea kunkin permutoinnin hinta. Palauta lopuksi vähimmäiskustannukset niiden joukkoon.

Huomautus: Tämä lähestymistapa ei ole toteutettavissa suuremmille syötteille, koska permutaatioiden määrä kasvaa kertoimella (m+n-2)!.
Jokaiselle permutaatiolle on laskettava kustannus O(m+n) ajassa. Siten kokonaisaikakompleksisuudeksi tulee O((m+n−2)!×(m+n)).

[Odotettu lähestymistapa] Ahneella tekniikalla - O(n (log n)+m (log m)) aika ja O(1)-avaruus

Ajatuksena on tehdä kalleimmat leikkaukset ensin käyttämällä a ahne lähestymistapa . Havainto on, että korkeimman kustannusleikkauksen valitseminen kussakin vaiheessa vähentää tulevia kustannuksia vaikuttamalla useisiin kappaleisiin kerralla. Lajittelemme pystysuoran (x) ja vaakasuuntaisen (y) kustannukset laskevaan järjestykseen ja valitsemme iteratiivisesti suuremman kustannussäästöjen maksimoimiseksi. Loput leikkaukset käsitellään erikseen, jotta kaikki osat jaetaan optimaalisesti.

Mitä tapahtuu, kun teemme leikkauksen?

• Vaakasuora leikkaus → leikkaat leveydeltä, jolloin vaakasuoroiden määrä kasvaa (hCount++). Mutta hinta kerrotaan vCount:lla (pystysuorien kaistaleiden määrä), koska vaakasuoran leikkauksen on läpäistävä kaikki pystysegmentit.
• Pystysuora leikkaus → leikkaat korkeuden poikki, jolloin pystysuorien kaistaleiden määrä kasvaa (vCount++). Mutta hinta kerrotaan hCount:lla (vaakasuuntaisten nauhojen määrä), koska pystysuoran leikkauksen on läpäistävä kaikki vaakasuorat segmentit.

Toimenpiteet ongelman ratkaisemiseksi:

• Lajittele sekä x - että y -taulukot laskevaan järjestykseen.
• Käytä kahta osoitinta x:lle ja y:lle alkaen suurimmasta arvosta ja siirry kohti pienempiä arvoja.
• Ylläpidä hCount ja vCount seurataksesi, kuinka moneen segmenttiin kukin leikkaus vaikuttaa, ja päivittää ne vastaavasti.
• Toista, kun sekä x:llä että y:llä on käsittelemättömiä leikkauksia, ja valitse aina suuremmat kustannukset kokonaiskustannusten minimoimiseksi.
• Jos x:llä on jäljellä leikkauksia, käsittele ne hCount-kertoimella; käsittele loput y-leikkaukset samalla tavalla vCount:lla.
• Kerää kokonaiskustannuksia kussakin vaiheessa käyttämällä kaavaa: vähennä kustannuksia * vaikuttavien kappaleiden määrä varmistaaksesi minimaaliset kustannukset.

#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