Dada la longitud de la pared w y los estantes de dos longitudes m y n, encuentre el número de cada tipo de estante que se usará y el espacio vacío restante en la solución óptima para que el espacio vacío sea mínimo. El más grande de los dos estantes es más barato, por lo que se prefiere. Sin embargo, el costo es secundario y la primera prioridad es minimizar el espacio vacío en la pared.
Ejemplos:
Input : w = 24 m = 3 n = 5 Output : 3 3 0 We use three units of both shelves and 0 space is left. 3 * 3 + 3 * 5 = 24 So empty space = 24 - 24 = 0 Another solution could have been 8 0 0 but since the larger shelf of length 5 is cheaper the former will be the answer. Input : w = 29 m = 3 n = 9 Output : 0 3 2 0 * 3 + 3 * 9 = 27 29 - 27 = 2 Input : w = 24 m = 4 n = 7 Output : 6 0 0 6 * 4 + 0 * 7 = 24 24 - 24 = 0
Un enfoque simple y eficiente será probar todas las combinaciones posibles de estantes que se ajusten a lo largo de la pared.
Para implementar este enfoque junto con la restricción de que el estante más grande cuesta menos que el más pequeño, a partir de 0, aumentamos el número de estantes más grandes hasta que puedan caber. Para cada caso calculamos el espacio vacío y finalmente almacenamos ese valor que minimiza el espacio vacío. si el espacio vacío es el mismo en dos casos, preferimos el que tiene más no de estantes más grandes.
A continuación se muestra su implementación.
C++
// C++ program to find minimum space and units
// of two shelves to fill a wall.
#include <bits/stdc++.h>
using namespace std;
void minSpacePreferLarge(int wall, int m, int n)
{
// for simplicity, Assuming m is always smaller than n
// initializing output variables
int num_m = 0, num_n = 0, min_empty = wall;
// p and q are no of shelves of length m and n
// rem is the empty space
int p = wall/m, q = 0, rem=wall%m;
num_m=p;
num_n=q;
min_empty=rem;
while (wall >= n) {
// place one more shelf of length n
q += 1;
wall = wall - n;
// place as many shelves of length m
// in the remaining part
p = wall / m;
rem = wall % m;
// update output variablse if curr
// min_empty <= overall empty
if (rem <= min_empty) {
num_m = p;
num_n = q;
min_empty = rem;
}
}
cout << num_m << " " << num_n << " "
<< min_empty << endl;
}
// Driver code
int main()
{
int wall = 29, m = 3, n = 9;
minSpacePreferLarge(wall, m, n);
wall = 76, m = 1, n = 10;
minSpacePreferLarge(wall, m, n);
return 0;
}
C
// C program to find minimum space and units
// of two shelves to fill a wall.
#include <stdio.h>
void minSpacePreferLarge(int wall, int m, int n)
{
// for simplicity, Assuming m is always smaller than n
// initializing output variables
int num_m = 0, num_n = 0, min_empty = wall;
// p and q are no of shelves of length m and n
// rem is the empty space
int p = wall / m, q = 0, rem = wall % m;
num_m = p;
num_n = q;
min_empty = rem;
while (wall >= n) {
// place one more shelf of length n
q += 1;
wall = wall - n;
// place as many shelves of length m
// in the remaining part
p = wall / m;
rem = wall % m;
// update output variablse if curr
// min_empty <= overall empty
if (rem <= min_empty) {
num_m = p;
num_n = q;
min_empty = rem;
}
}
printf("%d %d %d\n", num_m, num_n, min_empty);
}
// Driver code
int main()
{
int wall = 29, m = 3, n = 9;
minSpacePreferLarge(wall, m, n);
wall = 76, m = 1, n = 10;
minSpacePreferLarge(wall, m, n);
return 0;
}
// This code is contributed by rexomkar.
Java
// Java program to count all rotation
// divisible by 4.
public class GFG {
static void minSpacePreferLarge(int wall, int m, int n)
{
// For simplicity, Assuming m is always smaller than n
// initializing output variables
int num_m = 0, num_n = 0, min_empty = wall;
// p and q are no of shelves of length m and n
// rem is the empty space
int p = wall/m, q = 0, rem=wall%m;
num_m=p;
num_n=q;
min_empty=rem;
while (wall >= n) {
q += 1;
wall = wall - n;
// place as many shelves of length m
// in the remaining part
p = wall / m;
rem = wall % m;
// update output variablse if curr
// min_empty <= overall empty
if (rem <= min_empty) {
num_m = p;
num_n = q;
min_empty = rem;
}
// place one more shelf of length n
q += 1;
wall = wall - n;
}
System.out.println(num_m + " " + num_n + " " + min_empty);
}
// Driver Code
public static void main(String[] args)
{
int wall = 24, m = 3, n = 5;
minSpacePreferLarge(wall, m, n);
wall = 24;
m = 4;
n = 7;
minSpacePreferLarge(wall, m, n);
}
}
// This code is contributed by Saket Kumar
Python3
def minSpacePreferLarge(w, m, n): # initialize result variables num_m = 0 num_n = 0 rem = w # p and q are no of shelves of length m & # n respectively. r is the remainder uncovered # wall length p = w//m q = 0 rem=w%m; num_m=p; num_n=q; min_empty=rem; while (w >= n): q += 1; w-= n; p = w // m r = w % m if (r <= rem): num_m = p num_n = q rem = r q += 1 w -= n print( str(int(num_m)) + " " + str(num_n) + " " + str(rem)) # Driver code w = 24 m = 3 n = 5 minSpacePreferLarge(w, m, n) w = 24 m = 4 n = 7 minSpacePreferLarge(w, m, n)
C#
// C# program to count all rotation
// divisible by 4.
using System;
class GFG {
static void minSpacePreferLarge(int wall, int m, int n)
{
// For simplicity, Assuming m is always smaller than n
// initializing output variables
int num_m = 0, num_n = 0, min_empty = wall;
// p and q are no of shelves of length m and n
// rem is the empty space
int p = wall/m, q = 0, rem=wall%m;
num_m=p;
num_n=q;
min_empty=rem;
while (wall >= n) {
q += 1;
wall = wall - n;
// place as many shelves of length m
// in the remaining part
p = wall / m;
rem = wall % m;
// update output variablse if curr
// min_empty <= overall empty
if (rem <= min_empty) {
num_m = p;
num_n = q;
min_empty = rem;
}
// place one more shelf of length n
q += 1;
wall = wall - n;
}
Console.WriteLine(num_m + " " + num_n + " " + min_empty);
}
// Driver code
static public void Main()
{
int wall = 24, m = 3, n = 5;
minSpacePreferLarge(wall, m, n);
wall = 24;
m = 4;
n = 7;
minSpacePreferLarge(wall, m, n);
}
}
// This code is contributed by Tushil.
PHP
<?php
// PHP program to find minimum space and units
// of two shelves to fill a wall.
function minSpacePreferLarge($wall, $m, $n)
{
// for simplicity, Assuming m is always smaller than n
// initializing output variables
$num_m = 0;
$num_n = 0;
$min_empty = $wall;
// p and q are no of shelves of length m and n
// rem is the empty space
$p = $wall/$m
$q = 0
$rem=$wall%$m;
$num_m=$p;
$num_n=$q;
$min_empty=$rem;
while ($wall >= $n)
{
$q += 1;
$wall = $wall - $n;
// place as many shelves of length m
// in the remaining part
$p = $wall / $m;
$rem = $wall % $m;
// update output variablse if curr
// min_empty <= overall empty
if ($rem <= $min_empty)
{
$num_m = $p;
$num_n = $q;
$min_empty = $rem;
}
// place one more shelf of length n
$q += 1;
$wall = $wall - $n;
}
echo $num_m , " ", $num_n , " ",
$min_empty ,"\n";
}
// Driver code
$wall = 24;
$m = 3;
$n = 5;
minSpacePreferLarge($wall, $m, $n);
$wall = 24;
$m = 4;
$n = 7;
minSpacePreferLarge($wall, $m, $n);
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript program to count all rotation divisible by 4.
function minSpacePreferLarge(wall, m, n)
{
// for simplicity, Assuming m is always smaller than n
// initializing output variables
let num_m = 0, num_n = 0, min_empty = wall;
// p and q are no of shelves of length m and n
// rem is the empty space
let p = parseInt(wall/m, 10), q = 0, rem=wall%m;
num_m=p;
num_n=q;
min_empty=rem;
while (wall >= n) {
// place one more shelf of length n
q += 1;
wall = wall - n;
// place as many shelves of length m
// in the remaining part
p = parseInt(wall / m, 10);
rem = wall % m;
// update output variablse if curr
// min_empty <= overall empty
if (rem <= min_empty) {
num_m = p;
num_n = q;
min_empty = rem;
}
}
document.write(num_m + " " + num_n + " " + min_empty + "</br>");
}
let wall = 29, m = 3, n = 9;
minSpacePreferLarge(wall, m, n);
wall = 76, m = 1, n = 10;
minSpacePreferLarge(wall, m, n);
</script>
Producción
0 3 2 6 7 0
Complejidad del tiempo: O(w/max(n,m))
Complejidad espacial: O(1)
Referencias : Pregunta de la pasantía de Sumologic
Este artículo es una contribución de Aditi Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA