Food Festival

In this approach, we will recursively try out all possible combinations of ingredients for each dish. Function is called with ‘INDEX’ = 0 and ‘targetSpice‘ equal to spiciness of the dish then we have two options either to pick the ingredient of a given index or not pick.

In the case of pick, we have to again call the function with the same index (as we can have multiple ingredients of the same type) with target spiciness reduced by the spiciness of the ingredient.

In case of not pick, we have to call the function with index+1 and the same ‘targetSpice’.

If the value of ‘targetSpice’ becomes 0 after ‘INDEX’ reaches the end of the array then it is a valid combination.

The combination with the minimum total amount of ingredients is chosen. The same process is repeated for all the dishes.

The steps are as follows:-

// Recursive function to find minimum ingredients

function getMinIngredirentsUtil(int index, int targetSpice, [int]ingredients):

1. If ‘INDEX’ is equal to size of the ‘INGREDIENTS’ array.
   • If ‘targetSpice’ is equal to 0 then return 0.
   • Else return 1e9.
2. Initailze the variable ‘ANS’.
3. Call the function getMinIngredirentsUtil with INDEX = INDEX+1 and same ‘targetSpice’ and store the returned value in ANS.
4. If the value of targetSpice >= INGREDIENTS[INDEX]
   • Call the function getMinIngredirentsUtil with INDEX = INDEX and targetSpice = targetSpice-INGREDIENTS[i].
   • Update the value of ANS with min of ANS and value returned by the above function call.
5. Return the value of ANS.

function getMinIngredients(int n, [int]dishes, [int]ingredients):

1. Initialize a variable ‘ANS’ with 0, denoting the minimum ingredients needed to make all the dishes.
2. Run a for loop from 0 to N-1
   • Call the function getMinIngredirentsUtil with INDEX=0 and ‘targetSpice’ = DISHES[i].
   • Add returned value to ‘ANS’
3. Return the value of the variable 'ANS'.

The recursive approach discussed before can be optimized using memoization. We can memoize the result for each state with a particular ‘INDEX’ and ‘targetSpice’. In this way we can save time from recalculating the already calculated results.

For memoization let us define a matrix 2 dimensional array ‘DP’ of size ‘N’ x 1000. 1000 is used because at max target value can be 1000 as per the constraints given in the problem.

DP[i][j] - Minimum no. of ingredients needed to make a dish with ‘j’ spiciness using ingredients with index >= i.

The steps are as follows:-

// Recursive function to find minimum ingredients

function getMinIngredirentsUtil(int index, int targetSpice, [int]ingredients, [ [ int ] ]dp):

1. If INDEX is equal to the size of ‘INGREDIENTS’ array.
   • If ‘targetSpice’ is equal to 0 then return 0.
   • Else return 1e9.
2. If value of DP[ ‘INDEX’ ][ ‘targetSpice’ ] is not equal to -1 return the value of DP[ ‘INDEX’ ][ ‘targetSpice’ ].
3. Initailze the variable ‘ANS’.
4. Call the function with INDEX = INDEX+1 and same ‘targetSpice’ and store the returned value in ‘ANS’.
5. f the value of targetSpice >= INGREDIENTS[ ‘INDEX’ ]
   • Call the function getMinIngredirentsUtil with INDEX = INDEX and targetSpice = targetSpice-INGREDIENTS[i].
   • Update the value of ANS with min of ‘ANS’ and value returned by the above function call.
6. Return the value of ANS and also store it in DP[ ‘INDEX’ ][ ‘targetSpice’ ].

function getMinIngredients(int n, [int]dishes, [int]ingredients):

1. Initialize a variable ‘ANS’ with 0, denoting the minimum ingredients needed to make all the dishes.
2. Initialize 2D array ‘DP’ of dimension N * 1000 with -1
3. Run a for loop from i = 0….N-1.
   • Call the function getMinIngredirentsUtil with index=0 and targetSpice = DISHES[i].
   • Add returned value to ‘ANS’
4. Return the value of the variable 'ANS'.

The idea is the same as memoization. We are going to use the recurrence relation used in memoization. Here we only need a one-dimensional array ‘DP’ for storing the results.

DP[i] - Minimum no. of ingredients to make a dish with spiciness I.

The steps are as follows:-

function getMinIngredients(int n, [int]dishes, [int]ingredients):

1. Initialize a variable ‘ANS’ with 0, denoting the minimum ingredients needed to make all the dishes.
2. Initialize 1D array ‘DP’ of dimension 1000 with 1e9.
3. Assign 0 to DP[0].
4. Run a for loop from i=1….1000
   • Run a for loop from j=0 to N-1
     • If the value of INGREDIENTS[j] <= i
       • Update the value of DP[i] ( DP[i] = min(DP[i],1+DP[i-INGREDIENTS[j]]).
5. Run a for loop from i = 0…N-1
   • Add the value of DP[ DISHES[i] ] to the ANS variable.
6. Return the value of ‘ANS’ variable.