Una persona quiere transferir plátanos a un destino que está a un kilómetro de distancia. Inicialmente tiene plátanos B y un camello. El camello no puede llevar más de C plátanos a la vez y se come un plátano cada kilómetro que recorre. Dados tres números enteros A , B y C , la tarea es encontrar el número máximo de plátanos que la persona puede transferir al destino utilizando el camello.
Nota: El problema dado es una versión generalizada del famoso rompecabezas Camel-Banana .
Ejemplos:
Entrada: A = 10, B = 30, C = 10
Salida: 5Entrada: A = 1000, B = 3000, C = 1000
Salida: 533
Enfoque: el problema dado se puede resolver con la ayuda de la Programación Dinámica usando Memoización usando los siguientes puntos clave:
- Se puede observar que la forma más efectiva de transferir plátanos es dividir el camino (u, v) que tiene A km en algunas partes más pequeñas. Supongamos que x es un punto de ruptura en el camino (u, v) . La opción óptima es transferir todas las bananas de u a x y luego de x a v .
- Puede haber cualquier número de puntos de interrupción en la ruta (u, v) tal que el recuento de puntos de interrupción < A .
- El número total de viajes que tiene que hacer el camello que puede llevar C plátanos a la vez para trasladar X plátanos a cualquier distancia se puede calcular mediante la fórmula 2 * X / C – 1 , si C es un factor de X (es decir, , X % C = 0 ) de lo contrario 2 * X / C+1 .
Usando las observaciones anteriores, el problema dado se puede resolver siguiendo los pasos a continuación:
- Considere una array 2D dp[][] , donde un estado dp[A][B] representa la cantidad máxima de plátanos que un camello puede transferir en una distancia de A km teniendo B plátanos inicialmente. Inicialice la array dp[][] con -1 .
- Cree una función recursiva para iterar sobre la ruta dada de A km y cree un punto de interrupción en cada índice válido y llame recursivamente a la función para la ruta restante.
- Memorice el número máximo de plátanos para cada estado y devuelva el valor memorizado si el estado actual ya está calculado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the overlapping state
int dp[1001][3001];
// Recursive function to find the maximum
// number of bananas that can be transferred
// to A distance using memoization
int recBananaCnt(int A, int B, int C)
{
// Base Case where count of bananas
// is less that the given distance
if (B <= A) {
return 0;
}
// Base Case where count of bananas
// is less that camel's capacity
if (B <= C) {
return B - A;
}
// Base Case where distance = 0
if (A == 0) {
return B;
}
// If the current state is already
// calculated
if (dp[A][B] != -1) {
return dp[A][B];
}
// Stores the maximum count of bananas
int maxCount = INT_MIN;
// Stores the number of trips to transfer
// B bananas using a camel of capacity C
int tripCount = B % C == 0 ? ((2 * B) / C) - 1
: ((2 * B) / C) + 1;
// Loop to iterate over all the
// breakpoints in range [1, A]
for (int i = 1; i <= A; i++) {
// Recursive call over the
// remaining path
int curCount
= recBananaCnt(A - i,
B - tripCount * i, C);
// Update the maxCount
if (curCount > maxCount) {
maxCount = curCount;
// Memoize the current value
dp[A][B] = maxCount;
}
}
// Return answer
return maxCount;
}
// Function to find the maximum number of
// bananas that can be transferred
int maxBananaCnt(int A, int B, int C)
{
// Initialize dp array with -1
memset(dp, -1, sizeof(dp));
// Function Call
return recBananaCnt(A, B, C);
}
// Driver Code
int main()
{
int A = 1000;
int B = 3000;
int C = 1000;
cout << maxBananaCnt(A, B, C);
return 0;
}
Java
// Java program of the above approach
public class GFG {
// Stores the overlapping state
final static int dp[][] = new int[1001][3001];
// Recursive function to find the maximum
// number of bananas that can be transferred
// to A distance using memoization
static int recBananaCnt(int A, int B, int C)
{
// Base Case where count of bananas
// is less that the given distance
if (B <= A) {
return 0;
}
// Base Case where count of bananas
// is less that camel's capacity
if (B <= C) {
return B - A;
}
// Base Case where distance = 0
if (A == 0) {
return B;
}
// If the current state is already
// calculated
if (dp[A][B] != -1) {
return dp[A][B];
}
// Stores the maximum count of bananas
int maxCount = Integer.MIN_VALUE;
// Stores the number of trips to transfer
// B bananas using a camel of capacity C
int tripCount = B % C == 0 ? ((2 * B) / C) - 1 : ((2 * B) / C) + 1;
// Loop to iterate over all the
// breakpoints in range [1, A]
for (int i = 1; i <= A; i++) {
// Recursive call over the
// remaining path
int curCount
= recBananaCnt(A - i,
B - tripCount * i, C);
// Update the maxCount
if (curCount > maxCount) {
maxCount = curCount;
// Memoize the current value
dp[A][B] = maxCount;
}
}
// Return answer
return maxCount;
}
// Function to find the maximum number of
// bananas that can be transferred
static int maxBananaCnt(int A, int B, int C)
{
// Initialize dp array with -1
for(int i = 0; i < 1001; i++)
for (int j = 0; j < 3001; j++)
dp[i][j] = -1;
// Function Call
return recBananaCnt(A, B, C);
}
// Driver Code
public static void main (String[] args) {
int A = 1000;
int B = 3000;
int C = 1000;
System.out.println(maxBananaCnt(A, B, C));
}
}
// This code is contributed by AnkThon
Python3
# Python program of the above approach # Stores the overlapping state dp = [[-1 for i in range(3001)] for j in range(1001)] # Recursive function to find the maximum # number of bananas that can be transferred # to A distance using memoization def recBananaCnt(A, B, C): # Base Case where count of bananas # is less that the given distance if (B <= A): return 0 # Base Case where count of bananas # is less that camel's capacity if (B <= C): return B - A # Base Case where distance = 0 if (A == 0): return B # If the current state is already # calculated if (dp[A][B] != -1): return dp[A][B] # Stores the maximum count of bananas maxCount = -2**32 # Stores the number of trips to transfer # B bananas using a camel of capacity C tripCount = ((2 * B) // C) - 1 if(B % C == 0 ) else ((2 * B) // C) + 1 # Loop to iterate over all the # breakpoints in range [1, A] for i in range(1,A+1): # Recursive call over the # remaining path curCount = recBananaCnt(A - i, B - tripCount * i, C) # Update the maxCount if (curCount > maxCount): maxCount = curCount # Memoize the current value dp[A][B] = maxCount # Return answer return maxCount # Function to find the maximum number of # bananas that can be transferred def maxBananaCnt(A, B, C): # Function Call return recBananaCnt(A, B, C) # Driver Code A = 1000 B = 3000 C = 1000 print(maxBananaCnt(A, B, C)) # This code is contributed by shivanisinghss2110
C#
// C# program of the above approach
using System;
public class GFG {
// Stores the overlapping state
static int[, ] dp = new int[1001, 3001];
// Recursive function to find the maximum
// number of bananas that can be transferred
// to A distance using memoization
static int recBananaCnt(int A, int B, int C)
{
// Base Case where count of bananas
// is less that the given distance
if (B <= A) {
return 0;
}
// Base Case where count of bananas
// is less that camel's capacity
if (B <= C) {
return B - A;
}
// Base Case where distance = 0
if (A == 0) {
return B;
}
// If the current state is already
// calculated
if (dp[A, B] != -1) {
return dp[A, B];
}
// Stores the maximum count of bananas
int maxCount = Int32.MinValue;
// Stores the number of trips to transfer
// B bananas using a camel of capacity C
int tripCount = B % C == 0 ? ((2 * B) / C) - 1
: ((2 * B) / C) + 1;
// Loop to iterate over all the
// breakpoints in range [1, A]
for (int i = 1; i <= A; i++) {
// Recursive call over the
// remaining path
int curCount
= recBananaCnt(A - i, B - tripCount * i, C);
// Update the maxCount
if (curCount > maxCount) {
maxCount = curCount;
// Memoize the current value
dp[A, B] = maxCount;
}
}
// Return answer
return maxCount;
}
// Function to find the maximum number of
// bananas that can be transferred
static int maxBananaCnt(int A, int B, int C)
{
// Initialize dp array with -1
for (int i = 0; i < 1001; i++)
for (int j = 0; j < 3001; j++)
dp[i, j] = -1;
// Function Call
return recBananaCnt(A, B, C);
}
// Driver Code
public static void Main(string[] args)
{
int A = 1000;
int B = 3000;
int C = 1000;
Console.WriteLine(maxBananaCnt(A, B, C));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Stores the overlapping state
// Initialize dp array with -1
let dp = new Array(1001);
for (let i = 0; i < dp.length; i++)
{
dp[i] = (new Array(3001).fill(-1))
}
// Recursive function to find the maximum
// number of bananas that can be transferred
// to A distance using memoization
function recBananaCnt(A, B, C)
{
// Base Case where count of bananas
// is less that the given distance
if (B <= A) {
return 0;
}
// Base Case where count of bananas
// is less that camel's capacity
if (B <= C) {
return B - A;
}
// Base Case where distance = 0
if (A == 0) {
return B;
}
// If the current state is already
// calculated
if (dp[A][B] != -1) {
return dp[A][B];
}
// Stores the maximum count of bananas
let maxCount = Number.MIN_VALUE;
// Stores the number of trips to transfer
// B bananas using a camel of capacity C
let tripCount = B % C == 0 ? Math.floor((2 * B) / C) - 1
: Math.floor((2 * B) / C) + 1;
// Loop to iterate over all the
// breakpoints in range [1, A]
for (let i = 1; i <= A; i++) {
// Recursive call over the
// remaining path
let curCount
= recBananaCnt(A - i,
B - tripCount * i, C);
// Update the maxCount
if (curCount > maxCount) {
maxCount = curCount;
// Memoize the current value
dp[A][B] = maxCount;
}
}
// Return answer
return maxCount;
}
// Function to find the maximum number of
// bananas that can be transferred
function maxBananaCnt(A, B, C) {
// Function Call
return recBananaCnt(A, B, C);
}
// Driver Code
let A = 1000;
let B = 3000;
let C = 1000;
document.write(maxBananaCnt(A, B, C));
// This code is contributed by Potta Lokesh
</script>
Producción:
533
Complejidad temporal: O(A*A*B)
Espacio auxiliar: O(A*B)
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