Hemos discutido una estrategia de minimización de pérdidas antes: Problema de secuenciación de trabajos: minimización de pérdidas . En este artículo, veremos otra estrategia que se aplica a un problema ligeramente diferente.
Se nos da una secuencia de N bienes de producción numerados del 1 al N. Cada bien tiene un volumen denotado por (Vi). La restricción es que una vez que se ha completado un bien, su volumen comienza a decaer en un porcentaje fijo (P) por día. Todos los bienes se descomponen al mismo ritmo y, además, cada bien tarda un día en completarse.
Estamos obligados a encontrar el orden en que se deben producir los bienes para que se maximice el volumen total de bienes.
Ejemplo 1:
Input: 4, 2, 151, 15, 1, 52, 12 and P = 10% Output: 222.503
Solución: En la secuencia óptima de trabajos, el volumen total de bienes que quedan al final de todos los trabajos es 222.503
Ejemplo-2:
Input: 3, 1, 41, 52, 15, 4, 1, 63, 12 and P = 20% Output: 145.742
Solución: En la secuencia óptima de trabajos, el volumen total de bienes que quedan al final de todos los trabajos es 145,72
Explicación:
Dado que este es un problema de optimización, podemos intentar resolver este problema usando un algoritmo codicioso. Cada día hacemos una selección entre los bienes que aún están por producir. Por lo tanto, todo lo que necesitamos es un criterio de selección local o heurístico, que cuando se aplica para seleccionar los puestos de trabajo nos dará el resultado óptimo.
En lugar de intentar maximizar el volumen, también podemos intentar minimizar las pérdidas. Dado que el volumen total que se puede obtener de todos los bienes también es constante, si minimizamos las pérdidas tenemos la garantía de obtener la respuesta óptima.
Ahora considere cualquier bien que tenga un volumen V
Pérdida después del día 1: PV
Pérdida después del día 2: PV + P(1-P)V o V(2P-P^2)
Pérdida después del día 3: V(2P-P^2) + P(1 – 2P + P ^2)V o V(3P – 3P^2 + P^3)
A medida que aumenta el día, las pérdidas también aumentan. Entonces, el truco sería asegurarse de que los productos no se mantengan inactivos después de la producción. Además, dado que debemos producir al menos un trabajo por día, debemos realizar trabajos de bajo volumen y luego realizar trabajos de alto volumen.
Esta estrategia funciona debido a dos factores.
- Los productos de alto volumen no se mantienen inactivos después de la producción.
- A medida que el volumen disminuye, la pérdida por día también disminuye, por lo que para bienes de bajo volumen, las pérdidas se vuelven insignificantes después de unos días.
Entonces, para obtener la solución óptima, producimos los productos de mayor volumen más adelante. Para el primer día seleccionar el bien de menor volumen y producirlo. Eliminar el bien producido de la lista de bienes. Para el día siguiente repetir lo mismo. Siga repitiendo mientras queden bienes por producir.
Al calcular el volumen total al final de la producción, tenga en cuenta que el bien producido en el día i tendrá
veces su volumen restante. Evidentemente, el bien producido en el día N (último día) tendrá intacto su volumen ya que 
Algoritmo:
Step 1: Add all the goods to a min-heap Step 2: Repeat following steps while Queue is not empty Extract the good at the head of the heap Print the good Remove the good from the heap [END OF LOOP] Step 4: End
Complejidad:
Realizamos exactamente N operaciones push() y pop(), cada una de las cuales requiere un tiempo de registro (N). Por lo tanto, la complejidad del tiempo es O( N * log(N) ).
A continuación se muestra la implementación de la solución.
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
void optimum_sequence_jobs(vector<int>& V, double P)
{
int j = 1, N = V.size() - 1;
double result = 0;
// Create a min-heap (priority queue)
priority_queue<int, vector<int>, greater<int> > Queue;
// Add all goods to the Queue
for (int i = 1; i <= N; i++)
Queue.push(V[i]);
// Pop Goods from Queue as long as it is not empty
while (!Queue.empty()) {
// Print the good
cout << Queue.top() << " ";
// Add the Queue to the vector
// so that total volume can be calculated
V[j++] = Queue.top();
Queue.pop();
}
// Calculating volume of goods left when all
// are produced. Move from right to left of
// sequence multiplying each volume by
// increasing powers of 1 - P starting from 0
for (int i = N; i >= 1; i--)
result += pow((1 - P), N - i) * V[i];
// Print result
cout << endl << result << endl;
}
// Driver code
int main()
{
// For implementation simplicity days are numbered
// from 1 to N. Hence 1 based indexing is used
vector<int> V{ -1, 3, 5, 4, 1, 2, 7, 6, 8, 9, 10 };
// 10% loss per day
double P = 0.10;
optimum_sequence_jobs(V, P);
return 0;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
static void optimum_sequence_jobs(int[] V,
double P)
{
int j = 1, N = V.length - 1;
double result = 0;
// Create a min-heap
// (priority queue)
PriorityQueue<Integer> Queue =
new PriorityQueue<>();
// Add all goods to the Queue
for (int i = 1; i <= N; i++)
Queue.add(V[i]);
// Pop Goods from Queue as
// long as it is not empty
while (!Queue.isEmpty())
{
// Print the good
System.out.print(Queue.peek() +
" ");
// Add the Queue to the vector
// so that total volume can
// be calculated
V[j++] = Queue.peek();
Queue.remove();
}
// Calculating volume of goods
// left when all are produced.
// Move from right to left of
// sequence multiplying each
// volume by increasing powers
// of 1 - P starting from 0
for (int i = N; i >= 1; i--)
result += Math.pow((1 - P),
N - i) * V[i];
// Print result
System.out.printf("\n%.2f\n",
result );
}
// Driver code
public static void main(String[] args)
{
// For implementation simplicity
// days are numbered from 1 to N.
// Hence 1 based indexing is used
int[] V = {-1, 3, 5, 4, 1,
2, 7, 6, 8, 9, 10};
// 10% loss per day
double P = 0.10;
optimum_sequence_jobs(V, P);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python implementation of the
# above approach
from heapq import heappop, heappush, heapify
# Function to find the optimum sequence
def optimum_sequence_jobs(V: list, P: float):
N = len(V) - 1
j = 1
result = 0
Queue = []
for i in V[1:]:
heappush(Queue, i)
while Queue:
top = heappop(Queue)
V[j] = top
print(top, end=" ")
j += 1
print()
# Calculationg with decay
for i in range(N, 0, -1):
result += V[i] * pow((1 - P), (N - i))
print(f"{result:.4f}")
if __name__ == "__main__":
V = [-1, 3, 5, 4, 1, 2, 7, 6, 8, 9, 10]
# 10% loss per day
P = 0.10
optimum_sequence_jobs(V, P)
# This code is contributed by kraanzu.
C#
// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
public class GFG{
static void optimum_sequence_jobs(int[] V,
double P)
{
int j = 1, N = V.Length - 1;
double result = 0;
// Create a min-heap
// (priority queue)
List<int> Queue =
new List<int>();
// Add all goods to the Queue
for (int i = 1; i <= N; i++)
Queue.Add(V[i]);
Queue.Sort();
// Pop Goods from Queue as
// long as it is not empty
while (Queue.Count!=0)
{
// Print the good
Console.Write(Queue[0] +
" ");
// Add the Queue to the vector
// so that total volume can
// be calculated
V[j++] = Queue[0];
Queue.RemoveAt(0);
}
// Calculating volume of goods
// left when all are produced.
// Move from right to left of
// sequence multiplying each
// volume by increasing powers
// of 1 - P starting from 0
for (int i = N; i >= 1; i--)
result += Math.Pow((1 - P),
N - i) * V[i];
// Print result
Console.Write("\n{0:F2}\n",
result );
}
// Driver code
public static void Main(String[] args)
{
// For implementation simplicity
// days are numbered from 1 to N.
// Hence 1 based indexing is used
int[] V = {-1, 3, 5, 4, 1,
2, 7, 6, 8, 9, 10};
// 10% loss per day
double P = 0.10;
optimum_sequence_jobs(V, P);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of the
// above approach
// function to rectify sorting of
// numerical values in Javascript
function sorter(a, b){
return a - b;
}
function optimum_sequence_jobs(V,P){
var j = 1, N = V.length - 1;
var result = 0;
// Since Javascript doesn't support priority queues
// create a copy of V and sort it in ascending order
// to simulate a priority queue
var Queue = [];
// Add all goods to the Queue
for(var i=1;i<=N;i++){
Queue[i]=V[i];
}
// Javascript treats elements as strings due to which
// the standard .sort() function will treat "10" to
// be smaller than "5" because "1" is smaller than "2".
// In order to rectify the situation, sorter is used
Queue.sort(sorter);
// Pop Goods from Queue as
// long as it is not empty
for(var i = 0; i < Queue.length - 1; i++){
// Print the good
document.write(Queue[i]+" ");
// Add the Queue to the vector
// so that total volume can
// be calculated
V[j]=Queue[i];
j++;
}
// Calculating volume of goods
// left when all are produced.
// Move from right to left of
// sequence multiplying each
// volume by increasing powers
// of 1 - P starting from 0
for (var i = N; i >= 1; i--){
result += ((Math.pow((1 - P),(N - i))) * V[i]);
}
// Print result
document.write("\n");
document.write(result.toFixed(4));
}
// For implementation simplicity
// days are numbered from 1 to N.
// Hence 1 based indexing is used
let V = [-1, 3, 5, 4, 1, 2, 7, 6, 8, 9, 10];
// 10% loss per day
var P = 0.10;
optimum_sequence_jobs(V, P);
// This code is contributed by shruti456rawal
</script>
1 2 3 4 5 6 7 8 9 10 41.3811
Publicación traducida automáticamente
Artículo escrito por Sayan Mahapatra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA