Minimikustannukset laudan leikkaamisesta neliöiksi
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 Hinta = 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: alenna 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 ; }
Java 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 = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; System . out . println ( minCost ( n m x y )); } }
Python def minCost ( n m 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__' : n m = 4 6 x = [ 2 1 3 1 4 ] y = [ 4 1 2 ] print ( minCost ( n m x y ))
C# 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 = 4 m = 6 ; int [] x = { 2 1 3 1 4 }; int [] y = { 4 1 2 }; Console . WriteLine ( minCost ( n m x y )); } }
JavaScript function minCost ( n m 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 = 4 m = 6 ; let x = [ 2 1 3 1 4 ]; let y = [ 4 1 2 ]; console . log ( minCost ( n m x y ));
Lähtö
42Luo tietokilpailu
