Dados N códigos de programa y sus respectivos tiempos de depuración en una array codeTime y un número entero WorkingSessionTime, el iésimo programa tarda codeTime[i] horas en finalizar. WorkingSessionTime define un umbral de tiempo, usted trabaja como máximo durante WorkingSessionTime horas consecutivas y luego toma un descanso. Si WorkingSessionTime es inferior a 6 horas, entonces se pueden tomar 2 sesiones de trabajo por día; de lo contrario, solo se puede tomar una sesión de trabajo por día.
La depuración debe finalizar siguiendo las siguientes condiciones:
- Se debe completar una secuencia de depuración en la misma sesión (en cualquier orden).
- La nueva tarea de depuración se puede iniciar inmediatamente después de finalizar la anterior.
La tarea es imprimir el número mínimo de días necesarios para depurar todos los programas siguiendo las condiciones anteriores. Suponga que WorkingSessionTime es mayor o igual que el elemento máximo en la array codeTime .
Ejemplos :
Entrada : codeTime[] = {1, 2, 3}, WorkingSessionTime = 3
Salida : 1
Explicación : en la primera sesión de trabajo, terminaremos la primera y la segunda tarea en 1+2 = 3 horas y podemos terminar la última tarea en la segunda sesión de trabajo , por lo que el total de 2 sesiones de trabajo necesarias para finalizar la tarea. WorkingSessionTime es inferior a 6, por lo que podemos tomar dos sesiones por día, por lo que el número mínimo de días será 1Entrada : codeTime [] = {1, 2, 3, 1, 1, 3}, WorkingSessionTime = 4
Salida : 2
Explicación : en la primera sesión de trabajo, terminaremos la primera y la tercera tarea en 1+3 = 4 horas y en la segunda sesión podemos terminar la cuarta y sexta tarea en 1+3 = 4 horas y en la tercera sesión podemos terminar la segunda y quinta tarea 2 + 1 = 3 horas. WorkingSessionTime es menos de 6, por lo que podemos tomar dos sesiones por día. El primer día haremos dos sesiones de trabajo y al día siguiente haremos una sesión de trabajo. Entonces, el número mínimo de días requeridos es 2
Enfoque: una solución simple es probar todos los órdenes posibles de tareas. Comience seleccionando el primer elemento de la array, marcándolo como visitado y repita las tareas restantes y descubra las sesiones mínimas entre todos los pedidos posibles. Es básicamente una solución basada en el seguimiento. Después de encontrar un número mínimo de sesiones, comprobaremos si las horas de trabajo de la sesión son inferiores a 6 o no. Si es inferior a 6, comprobaremos además que ninguna de las sesiones mínimas es par o impar.
Enfoque óptimo : una mejor solución es utilizar Bitmasking y DP
La idea es usar el hecho de que hay hasta 14 tareas, por lo que podemos usar una variable entera como máscara para indicar qué elementos se procesan . si el i-ésimo bit está apagado , significa que la tarea i-ésima aún no se ha procesado con el tiempo restante que tenemos para la sesión actual. Si se establece el bit i-ésimo , significa que se procesa la tarea de depuración del código de programa i-ésimo.
- Inicialice la máscara como 000…000, que representa los estados iniciales (sin procesar) de todos los elementos.
- Pase el tiempo restante como 0, lo que significa que no hay tiempo restante para la sesión actual y tenemos que crear una nueva sesión.
- Compruebe si el i-ésimo bit está procesado o no, realice llamadas si la tarea no está procesada . si la tarea de depuración del código del programa no está procesada, márquela como procesada.
- Si el tiempo restante es mayor que CodeTime[i], incluiremos una tarea de depuración del código del programa en la sesión actual y actualizaremos el tiempo restante; de lo contrario, tendremos que crear una nueva sesión y aumentar el número de sesiones en 1.
- Una vez que se procesan todos los elementos o la máscara se convierte en 1, obtendremos el mínimo de sesiones posibles.
- Si el tiempo de sesión de trabajo es inferior a 6, comprobaremos además que el número mínimo de sesiones posibles es par o impar, si el número mínimo de días pares será la mitad del número mínimo de sesiones y si es el número mínimo de días impares. la mitad del número mínimo de sesiones +1, en caso contrario será igual un número mínimo de días para contestar.
Para lidiar con los subproblemas superpuestos, cree una tabla DP 2D para almacenar las respuestas de los subproblemas . Para cada elemento dp[i][j], i es la máscara y j es el tiempo restante.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the minimum work sessions
int minSessions(vector<int>& codeTime,
vector<vector<int> >& dp,
int ones, int n,
int mask, int currTime,
int WorkingSessionTime)
{
// Break condition
if (currTime > WorkingSessionTime)
return INT_MAX;
// All bits are set
if (mask == ones)
return 1;
// Check if already calculated
if (dp[mask][currTime] != -1)
return dp[mask][currTime];
// Store the answer
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
// Check if ith bit is set or unset
if ((mask & (1 << i)) == 0) {
// Including in current work session
int inc = minSessions(
codeTime, dp, ones,
n, mask | (1 << i),
currTime + codeTime[i],
WorkingSessionTime);
// Including in next work session
int inc_next
= 1
+ minSessions(
codeTime, dp, ones, n,
mask | (1 << i), codeTime[i],
WorkingSessionTime);
// Resultant answer will be minimum of both
ans = min({ ans, inc, inc_next });
}
}
return dp[mask][currTime] = ans;
}
// Function to initialize DP array
// and solve the problem
int solve(vector<int> codeTime, int n,
int WorkingSessionTime)
{
// Initialize dp table with -1
vector<vector<int> > dp((1 << 14),
vector<int>(15, -1));
// Resultant mask
int ones = (1 << n) - 1;
int ans = minSessions(codeTime, dp,
ones, n, 0, 0,
WorkingSessionTime);
// no. of minimum work sessions is even
if (WorkingSessionTime < 6) {
if (ans % 2 == 0)
ans = ans / 2;
// no. of minimum work sessions is odd
else
ans = (ans / 2) + 1;
}
return ans;
}
// Driver code
int main()
{
vector<int> codeTime = { 1, 2, 3, 1, 1, 3 };
int n = codeTime.size();
int WorkingSessionTime = 4;
cout
<< solve(codeTime, n, WorkingSessionTime)
<< endl;
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG
{
// Function to calculate
// the minimum work sessions
public static int minSessions(int[] codeTime, int[][] dp,
int ones, int n, int mask,
int currTime,
int WorkingSessionTime)
{
// Break condition
if (currTime > WorkingSessionTime)
return Integer.MAX_VALUE;
// All bits are set
if (mask == ones)
return 1;
// Check if already calculated
if (dp[mask][currTime] != -1)
return dp[mask][currTime];
// Store the answer
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// Check if ith bit is set or unset
if ((mask & (1 << i)) == 0) {
// Including in current work session
int inc = minSessions(codeTime, dp, ones, n,
mask | (1 << i), currTime +
codeTime[i], WorkingSessionTime);
// Including in next work session
int inc_next = 1 + minSessions(codeTime, dp,
ones, n, mask | (1 << i),
codeTime[i], WorkingSessionTime);
// Resultant answer will be minimum of both
ans = Math.min(ans, Math.min(inc, inc_next));
}
}
return dp[mask][currTime] = ans;
}
// Function to initialize DP array
// and solve the problem
public static int solve(int[] codeTime, int n,
int WorkingSessionTime)
{
// Initialize dp table with -1
int[][] dp = new int[(1 << 14)][];
for (int i = 0; i < 1 << 14; i++) {
dp[i] = new int[15];
Arrays.fill(dp[i], -1);
}
// Resultant mask
int ones = (1 << n) - 1;
int ans = minSessions(codeTime, dp,
ones, n, 0, 0,
WorkingSessionTime);
// no. of minimum work sessions is even
if (WorkingSessionTime < 6)
{
if (ans % 2 == 0)
ans = ans / 2;
// no. of minimum work sessions is odd
else
ans = (ans / 2) + 1;
}
return ans;
}
// Driver code
public static void main(String args[]) {
int[] codeTime = { 1, 2, 3, 1, 1, 3 };
int n = codeTime.length;
int WorkingSessionTime = 4;
System.out.println(solve(codeTime, n, WorkingSessionTime));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# Python 3 program for the above approach import sys # Function to calculate # the minimum work sessions def minSessions(codeTime, dp, ones, n, mask, currTime, WorkingSessionTime): # Break condition if (currTime > WorkingSessionTime): return sys.maxsize # All bits are set if (mask == ones): return 1 # Check if already calculated if (dp[mask][currTime] != -1): return dp[mask][currTime] # Store the answer ans = sys.maxsize for i in range(n): # Check if ith bit is set or unset if ((mask & (1 << i)) == 0): # Including in current work session inc = minSessions(codeTime, dp, ones, n, mask | (1 << i),currTime + codeTime[i],WorkingSessionTime) # Including in next work session inc_next = 1 + minSessions(codeTime, dp, ones, n,mask | (1 << i), codeTime[i],WorkingSessionTime) # Resultant answer will be minimum of both ans = min([ans, inc, inc_next]) dp[mask][currTime] = ans return ans # Function to initialize DP array # and solve the problem def solve(codeTime, n, WorkingSessionTime): # Initialize dp table with -1 dp = [[-1 for i in range(15)] for j in range(1 << 14)] # Resultant mask ones = (1 << n) - 1 ans = minSessions(codeTime, dp, ones, n, 0, 0, WorkingSessionTime) # no. of minimum work sessions is even if (WorkingSessionTime < 6): if (ans % 2 == 0): ans = ans // 2 # no. of minimum work sessions is odd else: ans = (ans / 2) + 1 return int(ans) # Driver code if __name__ == '__main__': codeTime = [1, 2, 3, 1, 1, 3] n = len(codeTime) WorkingSessionTime = 4 print(solve(codeTime, n, WorkingSessionTime)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to calculate
// the minimum work sessions
public static int minSessions(int[] codeTime, int[, ] dp,
int ones, int n, int mask,
int currTime,
int WorkingSessionTime)
{
// Break condition
if (currTime > WorkingSessionTime)
return Int32.MaxValue;
// All bits are set
if (mask == ones)
return 1;
// Check if already calculated
if (dp[mask, currTime] != -1)
return dp[mask, currTime];
// Store the answer
int ans = Int32.MaxValue;
for (int i = 0; i < n; i++) {
// Check if ith bit is set or unset
if ((mask & (1 << i)) == 0) {
// Including in current work session
int inc = minSessions(codeTime, dp, ones, n,
mask | (1 << i), currTime +
codeTime[i], WorkingSessionTime);
// Including in next work session
int inc_next = 1 + minSessions(codeTime, dp,
ones, n, mask | (1 << i),
codeTime[i], WorkingSessionTime);
// Resultant answer will be minimum of both
ans = Math.Min(ans, Math.Min(inc, inc_next));
}
}
return dp[mask, currTime] = ans;
}
// Function to initialize DP array
// and solve the problem
public static int solve(int[] codeTime, int n,
int WorkingSessionTime)
{
// Initialize dp table with -1
int[, ] dp = new int[(1 << 14), 15];
for (int i = 0; i < 1 << 14; i++) {
for(int j = 0; j < 15; j++) {
dp[i, j] = -1;
}
}
// Resultant mask
int ones = (1 << n) - 1;
int ans = minSessions(codeTime, dp,
ones, n, 0, 0,
WorkingSessionTime);
// no. of minimum work sessions is even
if (WorkingSessionTime < 6)
{
if (ans % 2 == 0)
ans = ans / 2;
// no. of minimum work sessions is odd
else
ans = (ans / 2) + 1;
}
return ans;
}
// Driver code
static public void Main (){
int[] codeTime = { 1, 2, 3, 1, 1, 3 };
int n = codeTime.Length;
int WorkingSessionTime = 4;
Console.WriteLine(solve(codeTime, n, WorkingSessionTime));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate
// the minimum work sessions
function minSessions(codeTime,
dp, ones, n, mask, currTime,
WorkingSessionTime)
{
// Break condition
if (currTime > WorkingSessionTime)
return Number.MAX_VALUE;
// All bits are set
if (mask == ones)
return 1;
// Check if already calculated
if (dp[mask][currTime] != -1)
return dp[mask][currTime];
// Store the answer
let ans = Number.MAX_VALUE;
for (let i = 0; i < n; i++)
{
// Check if ith bit is set or unset
if ((mask & (1 << i)) == 0)
{
// Including in current work session
let inc = minSessions(
codeTime, dp, ones,
n, mask | (1 << i),
currTime + codeTime[i],
WorkingSessionTime);
// Including in next work session
let inc_next = 1 + minSessions(
codeTime, dp, ones, n,
mask | (1 << i), codeTime[i],
WorkingSessionTime);
// Resultant answer will be minimum of both
ans = Math.min(ans, Math.min(inc, inc_next));
}
}
return dp[mask][currTime] = ans;
}
// Function to initialize DP array
// and solve the problem
function solve(codeTime, n,
WorkingSessionTime) {
// Initialize dp table with -1
let dp = new Array(1 << 14);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(15).fill(-1);
}
// Resultant mask
let ones = (1 << n) - 1;
let ans = minSessions(codeTime, dp,
ones, n, 0, 0,
WorkingSessionTime);
// no. of minimum work sessions is even
if (WorkingSessionTime < 6) {
if (ans % 2 == 0)
ans = Math.floor(ans / 2);
// no. of minimum work sessions is odd
else
ans = Math.floor(ans / 2) + 1;
}
return ans;
}
// Driver code
let codeTime = [1, 2, 3, 1, 1, 3];
let n = codeTime.length;
let WorkingSessionTime = 4;
document.write(
solve(codeTime, n, WorkingSessionTime))
// This code is contributed by Potta Lokesh
</script>
2
Complejidad de tiempo : O (2 ^ N * WorkingSessionTime * N), aquí N es la longitud de la array codeTime.
Espacio auxiliar : O(2^N * WorkingSessionTime), tamaño de la tabla dp.
Publicación traducida automáticamente
Artículo escrito por iramkhalid24 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA