Maximum Boxes

• The idea is to use recursion to reduce the big problem into several small subproblems.
• We will call a maximumBoxesHelper function that returns us the maximum boxes.
• The recursive relation used here is pretty simple, the points to be considered are:
  • If the number of apples is less than the minimum capacity among all the given boxes, we don’t have a way for that.
  • As we have three possible ways and we need to find the maximum count of boxes. We need to make recursive calls for each choice individually, thus, we make 3 recursive calls.
• Thus, the relation becomes:
  
  Function(N, A, B, C):
• Base case: If N is less than min(A, min(B, C))
  • Return 0.
• Recursive calls:
  • MAX of the following 3 recursive calls:
    • 1 + Function(N - A, A, B, C)
    • 1 + Function(N - B, A, B, C)
    • 1 + Function(N - C, A, B, C)
       
• The algorithm for the maximumBoxesHelper function will be as follows: 
  
  Int maximumBoxesHelper( N, A, B, C):
• If N == 0, return 0.
• If N is less than the minimum of { A, B and C}
  • return INT_MIN, as there is no possible way.
• Initialize ans = INT_MIN
• If N is greater than equal to A:
  • Call, ans = max(ans , 1 + maximumBoxesHelper( N-A, A, B, C).
• If  N is greater than equal to B:
  • Call, ans = max(ans , 1 + maximumBoxesHelper( N-B, A, B, C).
• If  N is greater than equal to C:
  • Call, ans = max(ans , 1 + maximumBoxesHelper( N-C, A, B, C).
• Return ans
• If ans is negative, it means no such arrangement is possible, so, the ans = 0.

To optimize the overlapping sub-problem calculation, we will use memoization by storing answers for each recursive state. We can see that we were solving the same subproblems multiple times. Thus, this problem was exhibiting overlapping subproblems. 

This means, in this approach, we need to eliminate the need for solving the same subproblems again and again. Thus, the idea is to use Memoization.

The steps are as follows:

1. Create a 'lookUp' table of size ‘N’ + 1 to store the answers to the subproblems where ‘lookUp[i]’ denotes the maximum possible boxes for ‘i’ number of apples.
2. Initialize the ‘lookUp’ array with -1 which denotes that it is not calculated yet.
3. We will call a maximumBoxesHelper function that returns us the maximum boxes.
4. The algorithm for the maximumBoxesHelper function will be as follows:
    

Int maximumBoxesHelper('N', ‘A’, ‘B’, ‘C’):

• If ‘N’ == 0, this means that we have no way to calculate the number of boxes, thus, return 0.
• If ‘N’ is less than minimum of ( ‘A’, ‘B’ and ‘C’}, return INT_MIN, as there is no possible way.
• If 'lookUp[N]' != -1, this means we have already calculated the answer for this sub-problem, return ‘lookUp[N]’.
• Initialize a variable ‘ANS’ = INT_MIN, this will store the final answer.
• Let’s consider choosing the box with capacity ‘A’, now, the number of apples left are ‘N’ - ‘A’ and 1 box is filled.
  • Thus,If ‘N’ is greater than equal to ‘A’, we call, ‘ANS’ = max( ‘ANS’ , 1 + maximumBoxesHelper( ‘N’ - ‘A’, ‘A’, ‘B’, ‘C’).
• In case we choose ‘B’:
  • If ‘N’ is greater than equal to ‘B’, call,  ‘ANS’ = max( ‘ANS’ , 1 + maximumBoxesHelper( ‘N’ - ‘B’, ‘A’, ‘B’, ‘C’).
• In case we choose ‘C’:
  • If ‘N’ is greater than equal to ‘C’,call,  ‘ANS’ = max( ‘ANS’ , 1 + maximumBoxesHelper( ‘N’ - ‘C’, ‘A’, 'B', ‘C’).
• Assign ‘lookUp[i]’ = ‘ANS’, to store it for further use.
• Return ‘ANS’.

Note: If ‘ANS’ is negative means no distribution is possible, so return ‘ANS’ = 0.

Initially, we were breaking the large problem into small problems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now. 

The steps are as follows:

1. The idea is to create a ‘DP' array of size ‘N’ + 1.
2. Initially, all the elements of the ‘DP’ array will be INT_MIN.
3. Now, the value ‘DP[i]' is the maximum possible boxes for ‘i’ apples. Thus, initialize ‘DP[0]’ as 0.

The detailed algorithm to fill the ‘DP’ array will be as follows:

Loop : For i = 1 to ‘N’:

• If ‘i' greater than or equal to ‘A’:
  • ‘DP[ i ]' = max ( ‘DP[ i ]’ , 1 + ‘DP[ i - A ]’ )
• If ‘i’ greater than or equal to ‘B’:
  • 'DP[ i ]' = max ( 'DP[ i ]' , 1 + 'DP[ i - B ]' )
• If ‘i’ greater than or equal to ‘C’:
  • ‘DP[ i ]’ = max ( ‘DP[ i ]’ , 1 + ‘DP[ i - C ]’ )
• So, our final ans is ‘DP[N]’.
   

Let us understand the algorithm with an example:

Consider ‘N’ = 5, ‘A’ = 2, ‘B’ = 3 and ‘C’ = 5

1. Firstly we create a ‘DP’ array of size ‘N’ + 1 i.e. 6 and assign INT_MIN to every index.
2. Initialize ‘DP[0]’ with 0.
3. The for loop begins: 
   
   
   • For ‘i’ = 1:
     • First if statement: as 1 is less than ‘A’, we won’t enter.
     • Second if statement: as 1 is less than ‘B’, we won’t enter.
     • Third if statement: as 1 is less than 5, we won’t enter.
     • Finally, ‘DP[1]’ = INT_MIN
        
   • For ‘i’ = 2:
     • First if statement passes, ‘DP[2]’ = max( ‘DP[2]’, 1 + ‘DP[ i - A ]’)
       ‘DP[2]’ = max( INT_MIN, 1 + ‘DP[0]’ )
       ‘DP[2]’ = max( INT_MIN, 1) i.e. 1.
     • Second if statement fails.
     • Third if statement fails.
     • Finally, ‘DP[2]’ = 1
        
   • For ‘i’ = 3:
     • First if statement passes, ‘DP[3]’ = max( ‘DP[3]', 1 + ‘DP[ i - ‘A’ ]’)
       ‘DP[3]’ = max( INT_MIN, 1 + ‘DP[1]’ )
       ‘DP[3]’ = max( INT_MIN, INT_MIN) i.e. INT_MIN.
     • Second if statement passes, ‘DP[3]’ = max( ‘DP[3]’, 1 + ‘DP[ i - ‘B’ ]’)
       ‘DP[3]' = max( INT_MIN, 1 + ‘DP[0]’ )
       ‘DP[3]’ = max( INT_MIN, 1) i.e. 1.
     • Third if statement fails.
     • Finally, ‘DP[3]’ = 1
        
   • For ‘i’ = 4:
     • First if statement passes, ‘DP[4]’ = max(' DP[4]', 1 + ‘DP[ i - ’A' ]')
       ‘DP[4]’ = max( INT_MIN, 1 + ‘DP[2]’ )
       ‘DP[4]’ = max( INT_MIN, 2) i.e. 2.
     • Second if statement passes, ‘DP[4]’ = max( ‘DP[4]’, 1 + ‘DP[ i - ’B' ]')
       ‘DP[4]' = max( 2, 1 + ‘DP[1]’ )
       ‘DP[4]’ = max( 2, INT_MIN) i.e. 2.
     • Third if statement fails.
     • Finally, 'DP[4]' = 2.
        
   • For ‘i’ = 5:
     • First if statement passes, ‘DP[5]’ = max( ‘DP[5]’, 1 + ‘DP[ i - ’A' ]')
       ‘DP[5]’ = max( INT_MIN, 1 + ‘DP[3]’ )
       ‘DP[5]’ = max( INT_MIN, 2) i.e. 2.
     • Second if statement passes, ‘DP[5]’ = max( ‘DP[5]’, 1 + ‘DP[ i - ’B' ]')
       ‘DP[5]’ = max( 2, 1 + ‘DP[2]’ )
       ‘DP[5]’ = max( 2, 2) i.e. 2.
     • Third if statement passes, ‘DP[5]’ = max( ‘DP[5]’, 1 + ‘DP[ i - ’C' ])
       ‘DP[5]’ = max( 2, 1 + ‘DP[0]’ )
       ‘DP[5]’ = max( 2, 0) i.e. 2.
        
4. Finally, ‘DP[5]’ = 2.
5. The for loop ends and ‘DP[ N ]’ contains our answer i.e. 2.