Dada una array 2D de placas[][] de tamaño N , en la que cada fila representa la longitud y el ancho de N placas rectangulares, la tarea es encontrar el número máximo de placas que se pueden colocar una sobre otra.
Nota: una placa se puede colocar sobre otra solo si su largo y ancho son estrictamente más pequeños que esa placa.
Ejemplos:
Entrada: Placas[][] = [ [3, 5], [6, 7], [7, 2], [2, 3] ]
Salida: 3
Explicación: Las placas se pueden organizar de esta manera [ 6, 7 ] => [3, 5] => [2, 3].Entrada: Placas[][] = [ [6, 4], [ 5, 7 ], [1, 2], [ 3, 3 ], [ 7, 9 ] ]
Salida: 4
Explicación: Las placas se pueden organizar de esta modo [ 7, 9 ] => [ 5, 7 ] => [ 3, 3 ] => [ 1, 2 ].
Enfoque: El problema es una variación del problema de la subsecuencia creciente más larga . La única diferencia es que en LIS , si i < j , entonces el i -ésimo elemento siempre vendrá antes que el j -ésimo elemento. Pero aquí, la elección de las placas no depende del índice. Entonces, para obtener esta restricción de índice, se requiere clasificar todas las placas en orden decreciente de área .
Si (i < j) y el área de la i -ésima placa también es mayor que la j -ésima placa, entonces la i -ésima placa siempre vendrá antes (abajo) de la j -ésima placa.
Enfoque recursivo :
Existen dos opciones posibles para cada placa, es decir, incluirla en la secuencia o descartarla. Solo se puede incluir una placa cuando su largo y ancho son menores que la placa anterior incluida.
El árbol de recurrencia para la array de placas[][] = [[6, 7], [3, 5], [7, 2]] es el siguiente:
A continuación se muestra la implementación del enfoque recursivo:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort plates
// in decreasing order of area
bool comp(vector<int> v1,
vector<int> v2)
{
return v1[0] * v1[1] > v2[0] * v2[1];
}
// Recursive function to count and return
// the max number of plates that can be placed
int countPlates(vector<vector<int> >& plates,
int lastLength, int lastWidth,
int i, int n)
{
// If no plate remains
if (i == n)
return 0;
int taken = 0, notTaken = 0;
// If length and width of previous plate
// exceeds that of the current plate
if (lastLength > plates[i][0]
&& lastWidth > plates[i][1]) {
// Calculate including the plate
taken = 1 + countPlates(plates, plates[i][0],
plates[i][1], i + 1, n);
// Calculate excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
}
// Otherwise
else
// Calculate only excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
return max(taken, notTaken);
}
// Driver code
int main()
{
vector<vector<int> > plates = { { 6, 4 }, { 5, 7 },
{ 1, 2 }, { 3, 3 }, { 7, 9 } };
int n = plates.size();
// Sorting plates in decreasing order of area
sort(plates.begin(), plates.end(), comp);
// Assuming first plate to be of maximum size
int lastLength = INT_MAX;
int lastWidth = INT_MAX;
cout << countPlates(plates, lastLength,
lastWidth, 0, n);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Recursive function to count and return
// the max number of plates that can be placed
static int countPlates(int[][] plates,
int lastLength,
int lastWidth,
int i, int n)
{
// If no plate remains
if (i == n)
return 0;
int taken = 0, notTaken = 0;
// If length and width of previous plate
// exceeds that of the current plate
if (lastLength > plates[i][0] &&
lastWidth > plates[i][1])
{
// Calculate including the plate
taken = 1 + countPlates(plates, plates[i][0],
plates[i][1], i + 1, n);
// Calculate excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
}
// Otherwise
else
// Calculate only excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
return Math.max(taken, notTaken);
}
// Driver code
public static void main(String[] args)
{
int[][] plates = { { 6, 4 }, { 5, 7 },
{ 1, 2 }, { 3, 3 }, { 7, 9 } };
int n = plates.length;
// Sorting plates in decreasing order of area
Arrays.sort(plates, (v1, v2)-> (v2[0] * v2[1]) -
(v1[0] * v1[1]));
// Assuming first plate to be of maximum size
int lastLength = Integer.MAX_VALUE;
int lastWidth = Integer.MAX_VALUE;
System.out.println(countPlates(plates, lastLength,
lastWidth, 0, n));
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript Program for the above approach
// Recursive function to count and return
// the max number of plates that can be placed
function countPlates(plates, lastLength,
lastWidth, i, n)
{
// If no plate remains
if (i == n)
return 0;
var taken = 0, notTaken = 0;
// If length and width of previous plate
// exceeds that of the current plate
if (lastLength > plates[i][0] &&
lastWidth > plates[i][1])
{
// Calculate including the plate
taken = 1 + countPlates(plates, plates[i][0],
plates[i][1], i + 1, n);
// Calculate excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
}
// Otherwise
else
// Calculate only excluding the plate
notTaken = countPlates(plates, lastLength,
lastWidth, i + 1, n);
return Math.max(taken, notTaken);
}
// Driver code
var plates = [ [ 6, 4 ], [ 5, 7 ],
[ 1, 2 ], [ 3, 3 ],
[ 7, 9 ] ];
var n = plates.length;
// Sorting plates in decreasing order of area
plates.sort((v1, v2) => v2[0] * v2[1] - v1[0] * v1[1]);
// Assuming first plate to be of maximum size
var lastLength = 1000000000;
var lastWidth = 1000000000;
document.write(countPlates(plates, lastLength,
lastWidth, 0, n));
// This code is contributed by rutvik_56
</script>
4
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar : O(N)
Enfoque de programación dinámica : el enfoque anterior se puede optimizar utilizando la programación dinámica como se ilustra a continuación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort plates
// in decreasing order of area
bool comp(vector<int> v1, vector<int> v2)
{
return v1[0] * v1[1] > v2[0] * v2[1];
}
// Function to count and return the max
// number of plates that can be placed
int countPlates(vector<vector<int> >& plates, int n)
{
// Stores the maximum
// number of plates
int maximum_plates = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
int cur = dp[i];
// For each i-th plate, traverse
// all the previous plates
for (int j = i - 1; j >= 0; j--) {
// If i-th plate is smaller than j-th plate
if (plates[i][0] < plates[j][0]
&& plates[i][1] < plates[j][1]) {
// Include the j-th plate only if current
// count exceeds the previously stored count
if (cur + dp[j] > dp[i]) {
dp[i] = cur + dp[j];
// Update the maximum count
maximum_plates = max(maximum_plates, dp[i]);
}
}
}
}
return maximum_plates;
}
// Driver code
int main()
{
vector<vector<int> > plates = { { 6, 4 }, { 5, 7 },
{ 1, 2 }, { 3, 3 }, { 7, 9 } };
int n = plates.size();
// Sorting plates in decreasing order of area
sort(plates.begin(), plates.end(), comp);
cout << countPlates(plates, n);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Function to count and return the max
// number of plates that can be placed
static int countPlates(ArrayList<plate> plates, int n)
{
// Stores the maximum
// number of plates
int maximum_plates = 1;
ArrayList<Integer> dp = new ArrayList<Integer>();
for(int i = 1 ; i <= n ; i++){
dp.add(1);
}
for (int i = 1; i < n; i++) {
int cur = dp.get(i);
// For each i-th plate, traverse
// all the previous plates
for (int j = i - 1 ; j >= 0 ; j--){
// If i-th plate is smaller than j-th plate
if (plates.get(i).l < plates.get(j).l && plates.get(i).b < plates.get(j).b) {
// Include the j-th plate only if current
// count exceeds the previously stored count
if (cur + dp.get(j) > dp.get(i)) {
dp.set(i, cur + dp.get(j));
// Update the maximum count
maximum_plates = Math.max(maximum_plates, dp.get(i));
}
}
}
}
return maximum_plates;
}
// Driver code
public static void main(String args[])
{
ArrayList<plate> plates = new ArrayList<plate>(
List.of(
new plate( 6, 4 ),
new plate( 5, 7 ),
new plate( 1, 2 ),
new plate( 3, 3 ),
new plate( 7, 9 )
)
);
int n = plates.size();
// Sorting plates in decreasing order of area
Collections.sort(plates, new comp());
System.out.println(countPlates(plates, n));
}
}
// Class for storing length and breadth of plate
class plate{
int l, b;
plate(int l,int b){
this.l = l;
this.b = b;
}
}
class comp implements Comparator<plate>
{
// Comparator function to sort plates
// in decreasing order of area
public int compare(plate o1, plate o2){
int x1 = o1.l*o1.b;
int x2 = o2.l*o2.b;
return x2-x1;
}
}
// This code is contributed by subhamgoyal2014.
Javascript
<script>
// Javascript program for the above approach
// Function to count and return the max
// number of plates that can be placed
function countPlates(plates, n)
{
// Stores the maximum
// number of plates
var maximum_plates = 1;
var dp = Array(n).fill(1);
for(var i = 1; i < n; i++)
{
var cur = dp[i];
// For each i-th plate, traverse
// all the previous plates
for(var j = i - 1; j >= 0; j--)
{
// If i-th plate is smaller than j-th plate
if (plates[i][0] < plates[j][0] &&
plates[i][1] < plates[j][1])
{
// Include the j-th plate only if
// current count exceeds the
// previously stored count
if (cur + dp[j] > dp[i])
{
dp[i] = cur + dp[j];
// Update the maximum count
maximum_plates = Math.max(
maximum_plates, dp[i]);
}
}
}
}
return maximum_plates;
}
// Driver code
var plates = [ [ 6, 4 ], [ 5, 7 ],
[ 1, 2 ], [ 3, 3 ],
[ 7, 9 ] ];
var n = plates.length;
// Sorting plates in decreasing order of area
plates.sort((v1, v2) => {
return((v2[0] * v2[1]) - (v1[0] * v1[1]));
});
document.write(countPlates(plates, n));
// This code is contributed by noob2000
</script>
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sachinjain74754 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA