Dada la altura y el ancho de N rectángulos. La tarea es encontrar el tamaño del subconjunto más grande de manera que ningún par de rectángulos encajen entre sí. Tenga en cuenta que si H1 ≤ H2 y W1 ≤ W2 , entonces el rectángulo 1 cabe dentro del rectángulo 2.
Ejemplos:
Entrada: arr[] = {{1, 3}, {2, 2}, {1, 3}}
Salida: 2
El subconjunto requerido es {{1, 3}, {2, 2}}
{1, 3} se incluye solo una vez, ya que puede caber en {1, 3}
Entrada: arr[] = {{1, 5}, {2, 4}, {1, 1}, {3, 3}} Salida
: 3
Enfoque: el problema anterior se puede resolver utilizando la programación dinámica y la clasificación . Inicialmente, podemos clasificar los N pares en función de las alturas. Se puede escribir una función recursiva donde habrá dos estados.
El primer estado es, si el rectángulo actual no encaja en el rectángulo anterior o viceversa, entonces llamamos al siguiente estado con el rectángulo actual siendo el rectángulo anterior y moviéndose al siguiente rectángulo.
dp[presente][anterior] = max(dp[presente][anterior], 1 + dp[presente + 1][presente])
Si encaja, llamamos al siguiente estado con el rectángulo anterior y pasamos al siguiente rectángulo.
dp[presente][anterior] = max(dp[presente][anterior], dp[presente + 1][anterior])
La memorización se puede utilizar además para evitar que se llamen repetitivamente a los mismos estados.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 10
int dp[N][N];
// Recursive function to get the largest subset
int findLongest(pair<int, int> a[], int n,
int present, int previous)
{
// Base case when it exceeds
if (present == n) {
return 0;
}
// If the state has been visited previously
else if (previous != -1) {
if (dp[present][previous] != -1)
return dp[present][previous];
}
// Initialize
int ans = 0;
// No elements in subset yet
if (previous == -1) {
// First state which includes current index
ans = 1 + findLongest(a, n,
present + 1, present);
// Second state which does not include current index
ans = max(ans, findLongest(a, n,
present + 1, previous));
}
else {
int h1 = a[previous].first;
int h2 = a[present].first;
int w1 = a[previous].second;
int w2 = a[present].second;
// If the rectangle fits in, then do not include
// the current index in subset
if ((h1 <= h2 && w1 <= w2)) {
ans = max(ans, findLongest(a, n,
present + 1, previous));
}
else {
// First state which includes current index
ans = 1 + findLongest(a, n,
present + 1, present);
// Second state which does not include current index
ans = max(ans, findLongest(a, n,
present + 1, previous));
}
}
return dp[present][previous] = ans;
}
// Function to get the largest subset
int getLongest(pair<int, int> a[], int n)
{
// Initialize the DP table with -1
memset(dp, -1, sizeof dp);
// Sort the array
sort(a, a + n);
// Get the answer
int ans = findLongest(a, n, 0, -1);
return ans;
}
// Driver code
int main()
{
// (height, width) pairs
pair<int, int> a[] = { { 1, 5 },
{ 2, 4 },
{ 1, 1 },
{ 3, 3 } };
int n = sizeof(a) / sizeof(a[0]);
cout << getLongest(a, n);
return 0;
}
Java
// Java implementation of the above approach.
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
public class GFG {
// A function to sort the 2D array by column number.
static void Sort(int[][] array, final int columnNumber)
{
Arrays.sort(array, new Comparator<int[]>() {
@Override
public int compare(int[] first, int[] second)
{
if (columnNumber >= 1
&& first[columnNumber - 1]
> second[columnNumber - 1])
return 1;
else
return -1;
}
});
}
// Recursive function to get the largest subset
static int findLongest(int[][] a, int n, int present,
int previous, int[][] dp, int N)
{
// Base case when it exceeds
if (present == n) {
return 0;
}
// If the state has been visited previously
else if (previous != -1) {
if (dp[present][previous] != -1)
return dp[present][previous];
}
// Initialize
int ans = 0;
// No elements in subset yet
if (previous == -1) {
// First state which includes current index
ans = 1
+ findLongest(a, n, present + 1, present,
dp, N);
// Second state which does not include current
// index
ans = Math.max(ans,
findLongest(a, n, present + 1,
previous, dp, N));
}
else {
int h1 = a[previous][0];
int h2 = a[present][0];
int w1 = a[previous][1];
int w2 = a[present][1];
// If the rectangle fits in, then do not include
// the current index in subset
if ((h1 <= h2 && w1 <= w2)) {
ans = Math.max(
ans, findLongest(a, n, present + 1,
previous, dp, N));
}
else {
// First state which includes current index
ans = 1
+ findLongest(a, n, present + 1,
present, dp, N);
// Second state which does not include
// current index
ans = Math.max(
ans, findLongest(a, n, present + 1,
previous, dp, N));
}
}
if (present >= 0 && previous >= 0) {
return dp[present][previous] = ans;
}
return ans;
}
// Function to get the largest subset
static int getLongest(int[][] a, int n)
{
int N = 10;
int[][] dp = new int[N + 1][N + 1];
// Initialize the DP table with -1
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < N + 1; j++) {
dp[i][j] = -1;
}
}
// Sort the array
Sort(a, 0);
// Get the answer
int ans = findLongest(a, n, 0, -1, dp, N);
return ans;
}
// Driver code
// (height, width) pairs
public static void main(String[] args)
{
int[][] a
= { { 1, 5 }, { 2, 4 }, { 1, 1 }, { 3, 3 } };
int n = a.length;
System.out.println(getLongest(a, n));
}
}
// The code is contributed by Gautam goel (guatamgoel962)
Python3
# Python3 implementation of the approach # Recursive function to get the # largest subset def findLongest(a, n, present, previous): # Base case when it exceeds if present == n: return 0 # If the state has been visited # previously elif previous != -1: if dp[present][previous] != -1: return dp[present][previous] # Initialize ans = 0 # No elements in subset yet if previous == -1: # First state which includes # current index ans = 1 + findLongest(a, n, present + 1, present) # Second state which does not # include current index ans = max(ans, findLongest(a, n, present + 1, previous)) else: h1 = a[previous][0] h2 = a[present][0] w1 = a[previous][1] w2 = a[present][1] # If the rectangle fits in, then do # not include the current index in subset if h1 <= h2 and w1 <= w2: ans = max(ans, findLongest(a, n, present + 1, previous)) else: # First state which includes # current index ans = 1 + findLongest(a, n, present + 1, present) # Second state which does not # include current index ans = max(ans, findLongest(a, n, present + 1, previous)) dp[present][previous] = ans return ans # Function to get the largest subset def getLongest(a, n): # Sort the array a.sort() # Get the answer ans = findLongest(a, n, 0, -1) return ans # Driver code if __name__ == "__main__": # (height, width) pairs a = [[1, 5], [2, 4], [1, 1], [3, 3]] N = 10 # Initialize the DP table with -1 dp = [[-1 for i in range(N)] for j in range(N)] n = len(a) print(getLongest(a, n)) # This code is contributed # by Rituraj Jain
Javascript
<script>
// JavaScript implementation of the approach
var N = 10;
var dp = Array.from(Array(N), ()=>Array(N).fill(-1));
// Recursive function to get the largest subset
function findLongest(a, n, present, previous)
{
// Base case when it exceeds
if (present == n) {
return 0;
}
// If the state has been visited previously
else if (previous != -1) {
if (dp[present][previous] != -1)
return dp[present][previous];
}
// Initialize
var ans = 0;
// No elements in subset yet
if (previous == -1) {
// First state which includes current index
ans = 1 + findLongest(a, n,
present + 1, present);
// Second state which does not include current index
ans = Math.max(ans, findLongest(a, n,
present + 1, previous));
}
else {
var h1 = a[previous][0];
var h2 = a[present][0];
var w1 = a[previous][1];
var w2 = a[present][1];
// If the rectangle fits in, then do not include
// the current index in subset
if ((h1 <= h2 && w1 <= w2)) {
ans = Math.max(ans, findLongest(a, n,
present + 1, previous));
}
else {
// First state which includes current index
ans = 1 + findLongest(a, n,
present + 1, present);
// Second state which does not include current index
ans = Math.max(ans, findLongest(a, n,
present + 1, previous));
}
}
return dp[present][previous] = ans;
}
// Function to get the largest subset
function getLongest(a, n)
{
// Initialize the DP table with -1
dp = Array.from(Array(N), ()=>Array(N).fill(-1));
// Sort the array
a.sort((a,b)=>a-b);
// Get the answer
var ans = findLongest(a, n, 0, -1);
return ans;
}
// Driver code
// (height, width) pairs
var a = [ [ 1, 5 ],
[ 2, 4 ],
[ 1, 1 ],
[ 3, 3 ] ];
var n = a.length;
document.write( getLongest(a, n));
</script>
Producción:
3
Complejidad de tiempo: O(N*N), donde las operaciones dp toman N*N tiempo
Espacio auxiliar: O(N*N), array dp formada por dos estados, cada uno con N espacio, es decir, N*N