SICK NINJA

We can recursively try out all the possible sets of fruits possible. We can add the nutrition and cost of each fruit we include in the set. We have two options for each fruit either to take it or not. We can recursively try out for both of these options and return the best of them. 

When we reach the end of the array, we can simply return the current value of nutrition and cost.

The steps are as follows:-
 

// Recursive function to find maximum strength

function  getMaxNutritionUtil(int index, [FRUIT] FRUITS,int N, 

                           int cost, int nutrition, int M ):
 

1. If index==N
   • If ( cost > M )
     • Return ( nutrition, cost ) = ( 0, 0 ).
   • Return ( nutrition, cost ).
2. Call getMaxNutritionUtil with ( index + 1, FRUITS, N, cost + FRUITS [ index ].cost, nutrition +  FRUITS [ index ].nutrition, M ) and store it in a variable ‘maxNutrition1’.
3. Call getMaxNutritionUtil with ( index + 1, FRUITS, N, cost, nutrition, M ) and store it in a variable ‘‘maxNutrition2’.
4. If ( ‘maxNutrition2.nutrition > ‘maxNutrition1.nutrition ).
   • Return ‘maxNutrition2’.
5. If ( maxNutrition2.nutrition == maxNutrition1.nutrition and maxNutrition2.cost < ‘maxNutrition1.cost).
   • Return ‘maxNutrition2’.
6. Return ‘maxNutrition1’.
    

function getMaxNutrition ( [FRUIT] FRUITS, int N, int M):

1. Call getMaxNutritionUtil with index as 0, cost as 0 and nutrition as 0 and store it in a variable ‘maxNutritionr’.
2. Return ‘maxNutrition’.

We can use the memoization technique to store the result for each state with a particular ‘index’ and ‘cost.’ This way, we can save time from recalculating the already calculated results.

For memoization, let us define a 2-dimensional matrix DP of size (N+1) * ( M + 1 ).

Where DP[ i ] [ j ] denotes the best possible values of nutrition and cost for index from ‘i’ to ‘N’ - 1 having already spent ‘j’ units of money.
 

The steps are as follows:-

      function  getMaxNutritionUtil(int index, [FRUIT] FRUITS,int N,

                      int cost, int M, [ FRUIT ] [ FRUIT ] DP ):

1. If index==’N’
   • Return ( cost, nutrition as 0 ).
2. If ( DP [ index ] [ cost ].cost != -1)
   • return DP [ index] [ cost].
3. Call getMaxNutritionUtil with ( index + 1, FRUITS, N, cost, M ) and store it in a variable ‘maxNutrition1’.
4. Update dp [ index ] [cost ] with ‘maxNutrition1’.
5. If ( cost + FRUITS [ index].cost <= M )
   • Call getMaxNutritionUtil with ( index + 1, FRUITS, N, cost + FRUITS [ index ].cost, nutrition , M ) and store it in ‘maxNutrition2’.
   • maxNutrition2.nutrition = maxNutrition2.nutrition +               fruits [ index ].cost
   • If ( maxNutrition2.nutrition > maxNutrition1.nutrition ).
     • DP [ index ] [ cost ] = ‘maxNutrition2’.
   • If ( maxNutrition2.nutrition == maxNutrition1.nutrition and maxNutrition2.cost < maxNutrition )
     • DP [ index] [ cost ] = maxNutrition2’.
6. Return DP [ index ] [ cost ].

function getMaxNutrition ( [ FRUIT] FRUITS, int N, int M):

1. Initialise a two dimensional matrix of size ( N + 1 ) * ( M +1 ) with cost and nutrition values as -1.
2. Call getMaxNutritionUtil with index as 0, cost as 0 and DP and store it in a variable ‘maxNutrition’.
3. Return ‘maxNutrition’.

The idea is the same as memoization. Here, we can use the idea of iterative dynamic programming. Let us define a 2-dimensional matrix DP of size (N+1) * ( M + 1 ).

 Where DP[ i ] [ j ] denotes the best possible values of nutrition and cost for index from ‘i’ to ‘N’ - 1 having already spent ‘j’ units of money.

 We have two options for each fruit when to take it or not. We can try out both of these options and store the best answer in the ‘DP’ matrix.

The steps are as follows:-

function getMaxNutrition ([FRUIT] FRUITS , int N ,int M)

1. Initialise a two-dimensional matrix of FRUIT  ‘DP’ of size (N+1) *(M+1).
2. Run a loop from i = ‘N’ to 0 :
   • Run a loop from j= 0 to ‘M’ :
     • If ( i  == N )
       • DP [ i ] [ j ]( cost, nutrition ) = (  j, 0 ) .
       • continue.
     • Initialise DP [ i ] [ j ] with DP [ i+1 ] [ j ]
     • If ( j + FRUITS [ i ] . cost <= M )
       • Initialise ‘maxNutrition1’ with DP [ i + 1 ] [ j + FRUITS [ i ].cost
       • maxNutrition1.nutrition =  maxNutrition1.nutrition + FRUITS [ i ].nutrition
       • If ( maxNutrition1.nutrition > DP [ i ] [ j ] . nutrition )
         1. DP [ i ] [ j ] = maxNutrition1.
       • If (  maxNutrition1.nutrition == DP [ i ] [ j ] and  maxNutrition1.cost < DP [ i ] [ j ] )
         1. DP [ i ] [ j ] = maxNutrition1.
3. return DP [ 0 ] [ 0 ] .