Dada una array arr[] que consta de N enteros positivos tales que arr[i] denota el tamaño del i -ésimo grupo sentado en una tienda de donas y un entero positivo K , que denota el número máximo de donas que se pueden servir en un lote , la tarea es encontrar el número máximo de grupos que pueden recibir donas frescas si los clientes del mismo grupo se sirven juntos.
Nota: todos los clientes de un grupo no reciben donas sobrantes del lote anterior.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Salida: 4
Explicación: Una forma posible de ordenar los grupos es {6, 2, 4, 5, 1, 3 }.
- arr[0](= 6), Las tiendas sirven dos lotes de 3 donas. Para que todos reciban donas frescas.
- arr[1](= 2), La tienda sirve 3 donas frescas, de las cuales 1 se queda fuera. Para que todos reciban donas frescas.
- arr[2](= 4), La tienda sirve primero 1 dona sobrante y luego sirve 3 donas frescas.
- arr[1](= 5), La tienda sirve 6 donas frescas, de las cuales 1 se queda fuera. Para que todos reciban donas frescas.
- arr[1](= 1), La tienda sirve 1 dona sobrante.
- arr[1](= 3), La tienda sirve 3 donas frescas. Para que todos reciban donas frescas.
Por lo tanto, un total de 4 grupos obtienen donas frescas, que es el número máximo posible de grupos.
Entrada: arr[] = {1, 3, 2, 5, 2, 2, 1, 6}, K = 4
Salida: 4
Enfoque ingenuo: el problema dado se puede resolver utilizando el retroceso para todos los pedidos posibles en función de la observación de que solo se debe considerar el resto del tamaño de cada grupo por K . Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos V[] de tamaño K , donde V[i] indica el número de grupos con i personas restantes.
- Recorra la array , arr[] usando la variable i y para cada arr[i], incremente el valor de V[arr[i] % K] en 1 .
- Defina una función recursiva, digamos dfs(V, izquierda) donde izquierda es el número de donas sobrantes del lote anterior:
- Inicialice una variable, res como 0 , para almacenar el resultado del estado actual.
- Si el valor de left es 0 , itere en el rango [1, K – 1] usando la variable i y realice los siguientes pasos:
- Disminuya el valor de V[i] en 1 y llame recursivamente a la función con el argumento left-i.
- Actualice res al máximo de dfs(V, izquierda – i) + 1 y res .
- Incremente el valor de V[i] en 1 para el paso de retroceso.
- De lo contrario, repita los mismos pasos anteriores, pero en este caso, no agregue 1 al resultado, ya que el grupo seleccionado obtendrá la dona sobrante.
- Devuelve el valor de res .
- Llame a la función recursiva definida anteriormente como dfs(V, 0) y almacene el valor devuelto en una variable, digamos X .
- Finalmente, después de completar los pasos anteriores, imprima la suma de V[0] y X como resultado.
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;
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
int dfs(int arr[], int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Check if the leftover donuts
// from the previous batch is 0
if (left == 0) {
// If true, then one by one
// give the fresh donuts
// to each group
for (int i = 1; i < K; ++i) {
if (arr[i] > 0) {
// Decrement arr[i]
arr[i]--;
// Update the maximum
// number of groups
q = max(q, 1 + dfs(arr, K - i, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Otherwise, traverse the given
// array, arr[]
else {
for (int i = 1; i < K; ++i) {
if (arr[i] > 0) {
// Decrement arr[i]
arr[i]--;
int nleft
= (i <= left ? left - i : K + left - i);
// Update the maximum
// number of groups
q = max(q, dfs(arr, nleft, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Return the value of q
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
int maxGroups(int K, int arr[], int n)
{
// Stores count of remainder
// by K
int V[K] = { 0 };
// Traverse the array arr[]
for (int x = 0; x < n; x++)
V[arr[x] % K]++;
// Stores maximum number of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << maxGroups(K, arr, n);
return 0;
}
// This code is contributed by Potta Lokesh
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
public static int dfs(int[] arr,
int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Check if the leftover donuts
// from the previous batch is 0
if (left == 0) {
// If true, then one by one
// give the fresh donuts
// to each group
for (int i = 1; i < K; ++i) {
if (arr[i] > 0) {
// Decrement arr[i]
arr[i]--;
// Update the maximum
// number of groups
q = Math.max(
q, 1 + dfs(arr, K - i, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Otherwise, traverse the given
// array, arr[]
else {
for (int i = 1; i < K; ++i) {
if (arr[i] > 0) {
// Decrement arr[i]
arr[i]--;
int nleft = (i <= left ? left - i
: K + left - i);
// Update the maximum
// number of groups
q = Math.max(q, dfs(arr, nleft, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Return the value of q
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
public static int maxGroups(int K,
int[] arr)
{
// Stores count of remainder
// by K
int V[] = new int[K];
// Traverse the array arr[]
for (int x : arr)
V[x % K]++;
// Stores maximum number of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int K = 3;
System.out.println(
maxGroups(K, arr));
}
}
Python3
# Python 3 program for the above approach # Recursive function to find the # maximum number of groups that # will receive fresh donuts def dfs(arr, left, K): # Store the result for the # current state q = 0 # Check if the leftover donuts # from the previous batch is 0 if (left == 0): # If true, then one by one # give the fresh donuts # to each group for i in range(1,K,1): if (arr[i] > 0): # Decrement arr[i] arr[i] -= 1 # Update the maximum # number of groups q = max(q, 1 + dfs(arr, K - i, K)) # Increment arr[i] arr[i] += 1 # Otherwise, traverse the given # array, arr[] else: for i in range(1,K,1): if (arr[i] > 0): # Decrement arr[i] arr[i] -= 1 nleft = left - i if i <= left else K + left - i # Update the maximum # number of groups q = max(q, dfs(arr, nleft, K)) # Increment arr[i] arr[i] += 1 # Return the value of q return q # Function to find the maximum # number of groups that will # receive fresh donuts def maxGroups(K, arr, n): # Stores count of remainder # by K V = [0 for i in range(K)] # Traverse the array arr[] for x in range(n): V[arr[x] % K] += 1 # Stores maximum number of groups ans = V[0] + dfs(V, 0, K) # Return the answer return ans # Driver Code if __name__ == '__main__': arr= [1, 2, 3, 4, 5, 6] n = len(arr) K = 3 print(maxGroups(K, arr, n)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
public static int dfs(int[] arr,
int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Check if the leftover donuts
// from the previous batch is 0
if (left == 0)
{
// If true, then one by one
// give the fresh donuts
// to each group
for(int i = 1; i < K; ++i)
{
if (arr[i] > 0)
{
// Decrement arr[i]
arr[i]--;
// Update the maximum
// number of groups
q = Math.Max(q, 1 + dfs(arr, K - i, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Otherwise, traverse the given
// array, arr[]
else
{
for(int i = 1; i < K; ++i)
{
if (arr[i] > 0)
{
// Decrement arr[i]
arr[i]--;
int nleft = (i <= left ? left - i :
K + left - i);
// Update the maximum
// number of groups
q = Math.Max(q, dfs(arr, nleft, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Return the value of q
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
public static int maxGroups(int K, int[] arr)
{
// Stores count of remainder
// by K
int[] V = new int[K];
// Traverse the array arr[]
foreach(int x in arr)
V[x % K]++;
// Stores maximum number of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int K = 3;
Console.WriteLine(maxGroups(K, arr));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
function dfs(arr, left, K)
{
// Store the result for the
// current state
let q = 0;
// Check if the leftover donuts
// from the previous batch is 0
if (left == 0)
{
// If true, then one by one
// give the fresh donuts
// to each group
for(let i = 1; i < K; ++i)
{
if (arr[i] > 0)
{
// Decrement arr[i]
arr[i]--;
// Update the maximum
// number of groups
q = Math.max(q, 1 + dfs(arr, K - i, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Otherwise, traverse the given
// array, arr[]
else
{
for(let i = 1; i < K; ++i)
{
if (arr[i] > 0)
{
// Decrement arr[i]
arr[i]--;
let nleft = (i <= left ? left - i :
K + left - i);
// Update the maximum
// number of groups
q = Math.max(q, dfs(arr, nleft, K));
// Increment arr[i]
arr[i]++;
}
}
}
// Return the value of q
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
function maxGroups(K, arr, n)
{
// Stores count of remainder
// by K
let V = new Array(K).fill(0);
// Traverse the array arr[]
for(let x = 0; x < n; x++)
V[arr[x] % K]++;
// Stores maximum number of groups
let ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver Code
let arr = [ 1, 2, 3, 4, 5, 6 ];
let n = arr.length;
let K = 3;
document.write(maxGroups(K, arr, n))
// This code is contributed by _Saurabh_jaiswal
</script>
Producción:
4
Complejidad temporal: O(N + K K )
Espacio auxiliar: O(K)
Enfoque eficiente: el enfoque anterior tiene subestructura óptima y subproblemas superpuestos , por lo tanto, el enfoque anterior también se puede optimizar memorizando las mismas llamadas recursivas en un HashMap y usar este estado cuando se llama recursivamente al mismo problema.
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;
// Stores the result of the same
// recursive calls
map<string, int> memo;
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
int dfs(int V[], int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Store the key and check
// if it is present in the
// hashmap
string key = "";
for(int i = 0; i < K; i++)
{
key = key + to_string(V[i]);
}
key += to_string(left);
// If already calculated
if (memo.find(key) != memo.end())
return memo[key];
// If left is 0
else if (left == 0) {
// Traverse the array []arr
for (int i = 1; i < K; ++i)
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
// Update the maximum
// number of groups
q = max(q, 1 + dfs(V, K - i, K));
// Increment arr[i] by 1
V[i]++;
}
}
// Otherwise, traverse the given
// array []arr
else {
for (int i = 1; i < K; ++i) {
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
int nleft = i <= left ? left - i : K + left - i;
// Update the maximum
// number of groups
q = max(q, dfs(V, nleft, K));
// Increment arr[i] by 1
V[i]++;
}
}
}
// Memoize the result and
// return it
if(memo.find(key) != memo.end())
memo[key] = q;
else
memo[key] = q;
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
int maxGroups(int K, int arr[])
{
// Stores count of remainder by K
int V[K];
memset(V, 0, sizeof(V));
// Traverse the array []arr
for (int i = 0; i < 6; i++)
V[arr[i] % K]++;
// Store the maximum number
// of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int K = 3;
cout << maxGroups(K, arr);
return 0;
}
// This code is contributed by divyeshrabadiya07.
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Stores the result of the same
// recursive calls
static HashMap<String, Integer> memo;
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
public static int dfs(int[] V,
int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Store the key and check
// if it is present in the
// hashmap
String key = Arrays.toString(V);
key += Integer.toString(left);
// If already calculated
if (memo.containsKey(key))
return memo.get(key);
// If left is 0
else if (left == 0) {
// Traverse the array arr[]
for (int i = 1; i < K; ++i)
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
// Update the maximum
// number of groups
q = Math.max(
q, 1 + dfs(V, K - i, K));
// Increment arr[i] by 1
V[i]++;
}
}
// Otherwise, traverse the given
// array arr[]
else {
for (int i = 1; i < K; ++i) {
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
int nleft = i <= left ? left - i
: K + left - i;
// Update the maximum
// number of groups
q = Math.max(q, dfs(V, nleft, K));
// Increment arr[i] by 1
V[i]++;
}
}
}
// Memoize the result and
// return it
memo.put(key, q);
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
public static int maxGroups(int K, int[] arr)
{
// Stores count of remainder by K
int V[] = new int[K];
// Traverse the array arr[]
for (int x : arr)
V[x % K]++;
// Hashmap to memoize the results
memo = new HashMap<String, Integer>();
// Store the maximum number
// of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int K = 3;
System.out.println(
maxGroups(K, arr));
}
}
Python3
# Python3 program for the above approach
# Stores the result of the same
# recursive calls
memo = {}
# Recursive function to find the
# maximum number of groups that
# will receive fresh donuts
def dfs(V, left, K):
# Store the result for the
# current state
q = 0
# Store the key and check
# if it is present in the
# hashmap
v = [str(int) for int in V]
key = ",".join(v)
key += str(left)
# If already calculated
if key in memo:
return memo[key]
# If left is 0
elif left == 0:
# Traverse the array []arr
for i in range(1, K):
if V[i] > 0:
# Decrement arr[i]
V[i]-=1
# Update the maximum
# number of groups
q = max(q, 1 + dfs(V, K - i, K))
# Increment arr[i] by 1
V[i]+=1
# Otherwise, traverse the given
# array []arr
else:
for i in range(1, K):
if V[i] > 0:
# Decrement arr[i]
V[i]-=1
if i <= left:
nleft = left - i
else:
nleft = K + left - i
# Update the maximum
# number of groups
q = max(q, dfs(V, nleft, K))
# Increment arr[i] by 1
V[i]+=1
# Memoize the result and
# return it
if key in memo:
memo[key] = q
else:
memo[key] = q
return q
# Function to find the maximum
# number of groups that will
# receive fresh donuts
def maxGroups(K, arr):
# Stores count of remainder by K
V = [0]*(K)
# Traverse the array []arr
for x in range(len(arr)):
V[arr[x] % K] += 1
# Hashmap to memoize the results
memo = {}
# Store the maximum number
# of groups
ans = V[0] + dfs(V, 0, K)
# Return the answer
return ans
arr = [ 1, 2, 3, 4, 5, 6 ]
K = 3
print(maxGroups(K, arr))
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Stores the result of the same
// recursive calls
static Dictionary<String, int> memo;
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
public static int dfs(int[] V,
int left, int K)
{
// Store the result for the
// current state
int q = 0;
// Store the key and check
// if it is present in the
// hashmap
String key = string.Join(",", V);
key += left.ToString();
// If already calculated
if (memo.ContainsKey(key))
return memo[key];
// If left is 0
else if (left == 0) {
// Traverse the array []arr
for (int i = 1; i < K; ++i)
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
// Update the maximum
// number of groups
q = Math.Max(
q, 1 + dfs(V, K - i, K));
// Increment arr[i] by 1
V[i]++;
}
}
// Otherwise, traverse the given
// array []arr
else {
for (int i = 1; i < K; ++i) {
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
int nleft = i <= left ? left - i
: K + left - i;
// Update the maximum
// number of groups
q = Math.Max(q, dfs(V, nleft, K));
// Increment arr[i] by 1
V[i]++;
}
}
}
// Memoize the result and
// return it
if(memo.ContainsKey(key))
memo[key] = q;
else
memo.Add(key, q);
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
public static int maxGroups(int K, int[] arr)
{
// Stores count of remainder by K
int []V = new int[K];
// Traverse the array []arr
foreach (int x in arr)
V[x % K]++;
// Hashmap to memoize the results
memo = new Dictionary<String, int>();
// Store the maximum number
// of groups
int ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int K = 3;
Console.WriteLine(
maxGroups(K, arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Stores the result of the same
// recursive calls
let memo;
// Recursive function to find the
// maximum number of groups that
// will receive fresh donuts
function dfs(V, left, K)
{
// Store the result for the
// current state
let q = 0;
// Store the key and check
// if it is present in the
// hashmap
let key = V.join(",");
key += left.toString();
// If already calculated
if (memo.has(key))
return memo[key];
// If left is 0
else if (left == 0) {
// Traverse the array []arr
for (let i = 1; i < K; ++i)
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
// Update the maximum
// number of groups
q = Math.max(q, 1 + dfs(V, K - i, K));
// Increment arr[i] by 1
V[i]++;
}
}
// Otherwise, traverse the given
// array []arr
else {
for (let i = 1; i < K; ++i) {
if (V[i] > 0) {
// Decrement arr[i]
V[i]--;
let nleft = i <= left ? left - i : K + left - i;
// Update the maximum
// number of groups
q = Math.max(q, dfs(V, nleft, K));
// Increment arr[i] by 1
V[i]++;
}
}
}
// Memoize the result and
// return it
if(memo.has(key))
memo[key] = q;
else
memo[key] = q;
return q;
}
// Function to find the maximum
// number of groups that will
// receive fresh donuts
function maxGroups(K, arr)
{
// Stores count of remainder by K
let V = new Array(K);
V.fill(0);
// Traverse the array []arr
for(let x = 0; x < arr.length; x++)
V[arr[x] % K]++;
// Hashmap to memoize the results
memo = new Map();
// Store the maximum number
// of groups
let ans = V[0] + dfs(V, 0, K);
// Return the answer
return ans;
}
let arr = [ 1, 2, 3, 4, 5, 6 ];
let K = 3;
document.write(maxGroups(K, arr));
// This code is contributed by rameshtravel07.
</script>
Producción:
4
Complejidad de Tiempo: O(N + K 2 )
Espacio Auxiliar: O(K)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA