Dada una array arr[] que consta de N enteros, la tarea es encontrar el costo mínimo para eliminar todos los elementos de la array de modo que el costo de eliminar cualquier elemento sea la diferencia absoluta entre el instante de tiempo actual T ( inicialmente 1 ) y el elemento de array arr[i] es decir, abs(T – arr[i]) donde T .
Ejemplos:
Entrada: arr[] = {3, 6, 4, 2}
Salida: 0
Explicación:
T = 1: Sin eliminación
T = 2: Eliminar arr[3]. Costo = |2 – 2| = 0
T = 3: Eliminar arr[0]. Costo = |3 – 3| = 0
T = 4: Eliminar arr[2]. Costo = |4 – 4| = 0
T = 5: Sin eliminación.
T = 6: Eliminar arr[1]. Coste = |0| + |6 – 6| = 0
Por lo tanto, el costo total = 0Entrada: arr[] = {4, 2, 4, 4, 5, 2}
Salida: 4
Enfoque ingenuo: la idea es utilizar la recursividad para resolver el problema. En cada instante de tiempo existen dos posibilidades, ya sea eliminar algún elemento o no. Por lo tanto, para minimizar el costo, ordene la array . Luego, comenzando desde el índice 0 y el tiempo T = 1 , resuelva el problema usando la siguiente relación de recurrencia:
minCost(index, time) = min(minCost(index + 1, T + 1) + abs(time – a[index]), minCost(index, T + 1))
donde, caso base: si el índice actual excede el actual tamaño de la array.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica , ya que existen subproblemas superpuestos y una subestructura superpuesta a la relación de recurrencia anterior. Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2-D , cost[][] de tamaño N*2N con un valor grande donde cost[i][j] denota el costo mínimo para eliminar todos los elementos hasta el i -ésimo índice de la array dada usando j cantidad de tiempo.
- Además, inicialice cost[0][0] con 0 y variable, prev con 0 donde prev almacenará el mínimo de todos los valores de costo anteriores del índice anterior.
- Recorra la array dada arr[] usando una variable i y luego, para cada i , itere en el rango [1, 2N] usando la variable j :
- Si el valor de (prev + abs(j – arr[i – 1]) es menor que cost[i][j] , actualice cost[i][j] a este valor.
- Si cost[i – 1][j] es menor que prev , actualice prev a este valor.
- Después de los pasos anteriores, imprima el costo mínimo como cost[N][j] .
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;
#define INF 10000
// Function to find the minimum cost
// to delete all array elements
void minCost(int arr[], int n)
{
// Sort the input array
sort(arr, arr + n);
// Store the maximum time to delete
// the array in the worst case
int m = 2 * n;
// Store the result in cost[][] table
int cost[n + 1][m + 1];
// Initialize the table cost[][]
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
cost[i][j] = INF;
}
}
// Base Case
cost[0][0] = 0;
// Store the minimum of all cost
// values of the previous index
int prev = 0;
// Iterate from range [1, n]
// using variable i
for (int i = 1; i <= n; i++) {
// Update prev
prev = cost[i - 1][0];
// Iterate from range [1, m]
// using variable j
for (int j = 1; j <= m; j++) {
// Update cost[i][j]
cost[i][j] = min(cost[i][j],
prev
+ abs(j - arr[i - 1]));
// Update the prev
prev = min(prev, cost[i - 1][j]);
}
}
// Store the minimum cost to
// delete all elements
int minCost = INF;
// Find the minimum of all values
// of cost[n][j]
for (int j = 1; j <= m; j++) {
minCost = min(minCost, cost[n][j]);
}
// Print minimum cost
cout << minCost;
}
// Driver Code
int main()
{
int arr[] = { 4, 2, 4, 4, 5, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
minCost(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
class GFG{
static int INF = 10000;
// Function to find the minimum cost
// to delete all array elements
static void minCost(int arr[], int n)
{
// Sort the input array
Arrays.sort(arr);
// Store the maximum time to delete
// the array in the worst case
int m = 2 * n;
// Store the result in cost[][] table
int cost[][] = new int[n + 1][m + 1];
// Initialize the table cost[][]
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
cost[i][j] = INF;
}
}
// Base Case
cost[0][0] = 0;
// Store the minimum of all cost
// values of the previous index
int prev = 0;
// Iterate from range [1, n]
// using variable i
for(int i = 1; i <= n; i++)
{
// Update prev
prev = cost[i - 1][0];
// Iterate from range [1, m]
// using variable j
for(int j = 1; j <= m; j++)
{
// Update cost[i][j]
cost[i][j] = Math.min(cost[i][j],
prev + Math.abs(
j - arr[i - 1]));
// Update the prev
prev = Math.min(prev, cost[i - 1][j]);
}
}
// Store the minimum cost to
// delete all elements
int minCost = INF;
// Find the minimum of all values
// of cost[n][j]
for(int j = 1; j <= m; j++)
{
minCost = Math.min(minCost, cost[n][j]);
}
// Print minimum cost
System.out.print(minCost);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 2, 4, 4, 5, 2 };
int N = arr.length;
// Function Call
minCost(arr, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach INF = 10000 # Function to find the minimum cost # to delete all array elements def minCost(arr, n): # Sort the input array arr = sorted(arr) # Store the maximum time to delete # the array in the worst case m = 2 * n # Store the result in cost[][] table cost = [[INF for i in range(m + 1)] for i in range(n + 1)] # Base Case cost[0][0] = 0 # Store the minimum of all cost # values of the previous index prev = 0 # Iterate from range [1, n] # using variable i for i in range(1, n + 1): # Update prev prev = cost[i - 1][0] # Iterate from range [1, m] # using variable j for j in range(1, m + 1): # Update cost[i][j] cost[i][j] = min(cost[i][j], prev + abs(j - arr[i - 1])) # Update the prev prev = min(prev, cost[i - 1][j]) # Store the minimum cost to # delete all elements minCost = INF # Find the minimum of all values # of cost[n][j] for j in range(1, m + 1): minCost = min(minCost, cost[n][j]) # Print minimum cost print(minCost) # Driver Code if __name__ == '__main__': arr=[4, 2, 4, 4, 5, 2] N = len(arr) # Function Call minCost(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
static int INF = 10000;
// Function to find the minimum cost
// to delete all array elements
static void minCost(int[] arr, int n)
{
// Sort the input array
Array.Sort(arr);
// Store the maximum time to delete
// the array in the worst case
int m = 2 * n;
// Store the result in cost[][] table
int[,] cost = new int[n + 1, m + 1];
// Initialize the table cost[][]
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= m; j++)
{
cost[i, j] = INF;
}
}
// Base Case
cost[0, 0] = 0;
// Store the minimum of all cost
// values of the previous index
int prev = 0;
// Iterate from range [1, n]
// using variable i
for(int i = 1; i <= n; i++)
{
// Update prev
prev = cost[i - 1, 0];
// Iterate from range [1, m]
// using variable j
for(int j = 1; j <= m; j++)
{
// Update cost[i][j]
cost[i, j] = Math.Min(cost[i, j],
prev + Math.Abs(
j - arr[i - 1]));
// Update the prev
prev = Math.Min(prev, cost[i - 1, j]);
}
}
// Store the minimum cost to
// delete all elements
int minCost = INF;
// Find the minimum of all values
// of cost[n][j]
for(int j = 1; j <= m; j++)
{
minCost = Math.Min(minCost, cost[n, j]);
}
// Print minimum cost
Console.Write(minCost);
}
// Driver Code
public static void Main()
{
int[] arr = { 4, 2, 4, 4, 5, 2 };
int N = arr.Length;
// Function Call
minCost(arr, N);
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program for above approach
let INF = 10000;
// Function to find the minimum cost
// to delete all array elements
function minCost(arr, n)
{
// Sort the input array
arr.sort();
// Store the maximum time to delete
// the array in the worst case
let m = 2 * n;
// Store the result in cost[][] table
let cost = new Array(n + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < cost.length; i++) {
cost[i] = new Array(2);
}
// Initialize the table cost[][]
for(let i = 0; i <= n; i++)
{
for(let j = 0; j <= m; j++)
{
cost[i][j] = INF;
}
}
// Base Case
cost[0][0] = 0;
// Store the minimum of all cost
// values of the previous index
let prev = 0;
// Iterate from range [1, n]
// using variable i
for(let i = 1; i <= n; i++)
{
// Update prev
prev = cost[i - 1][0];
// Iterate from range [1, m]
// using variable j
for(let j = 1; j <= m; j++)
{
// Update cost[i][j]
cost[i][j] = Math.min(cost[i][j],
prev + Math.abs(
j - arr[i - 1]));
// Update the prev
prev = Math.min(prev, cost[i - 1][j]);
}
}
// Store the minimum cost to
// delete all elements
let minCost = INF;
// Find the minimum of all values
// of cost[n][j]
for(let j = 1; j <= m; j++)
{
minCost = Math.min(minCost, cost[n][j]);
}
// Print minimum cost
document.write(minCost);
}
// Driver Code
let arr = [ 4, 2, 4, 4, 5, 2 ];
let N = arr.length;
// Function Call
minCost(arr, N);
// This code is contributed by avijitmondal1998.
</script>
Producción:
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por ananyadixit8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA