Camel and Banana Puzzle | DP

19 June 2025

0

A person wants to transfer bananas over to a destination A km away. He initially has B bananas and a camel. The camel cannot carry more than C bananas at a time and eats a banana every km it travels. Given three integers A, B, and C, the task is to find the maximum number of bananas the person can transfer to the destination using the camel.

Note: The given problem is a generalized version of the famous Camel-Banana puzzle.

Examples:

Input: A = 10, B = 30, C = 10
Output: 5

Input: A = 1000, B = 3000, C = 1000
Output: 533

Approach: The given problem can be solved with the help of Dynamic Programming using Memoization using the following key points:

It can be observed that the most effective way to transfer bananas is to divide the path (u, v) having A km into some smaller parts. Suppose x is a breakpoint in the path (u, v). The optimal choice is to transfer all the bananas from u to x and then from x to v.
There can be any number of breakpoints in the path (u, v) such that the count of breakpoints < A.
The total number of trips the camel which can carry C bananas at a time has to make in order to transfer X bananas over any distance can be calculated by the formula 2 * X / C – 1, if C is a factor of X (i.e, X % C = 0) otherwise 2 * X / C +1.

Using the above observations, the given problem can be solved by following the below steps:

Consider a 2D array dp[][], where a state dp[A][B] represents the maximum number of bananas a camel can transfer over a distance of A km having B bananas initially. Initialize the dp[][] array with -1.
Create a recursive function to iterate over the given path of A km and create a breakpoint at each valid index and recursively call the function for the remaining path.
Memoize the maximum number of bananas for each state and return the memoized value if the current state is already calculated.

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(A*A*B)
Auxiliary Space: O(A*B)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Camel and Banana Puzzle | DP

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US