Umbrella

Approach: The idea here is to try every possible option and consider the minimum ans.

 We have two possible options: either we use the i-th umbrella to cover people or not. 

So, the recurrence for the above problem is:

minNumberOfUmbrellas(i, M) = min(minNumberOfUmbrellas(i - 1, M), 1+ minNumberOfUmbrellas(i, M - UMBRELLA[i])).

minNumberOfUmbrellas(i, M) represents the minimum number of umbrellas required to shelter M people with first i umbrellas.

If we skip the i-th umbrella then the sub-problem is the same as solving for minNumberOfUmbrellas(i - 1, M) - a minimum number of umbrellas required to shelter M people with the first i - 1 umbrella.

If we consider the i-th umbrella then the sub-problem is the same as solving for 1 + minNumberOfUmbrellas(i, M - UMBRELLA[i]) - a minimum number of umbrellas required to shelter M - UMBRELLA[i] people with first i umbrellas (since we have an infinite umbrella of i-th type). Since we are considering the i-th umbrella we add 1 to the sub-problem.
 

The algorithm is as follows:

1. Declare a minNumberOfUmbrellas function with parameters i, M, UMBRELLA where i represents the index for the i-th umbrella we are taking, M is the required number of people to shelter and UMBRELLA is the array passed in the input.
   • If M equals 0, If the required number of people to shelter is 0 then we don’t require any umbrellas.
     • Return 0.
   • Else If i equals 0, then we don’t have any umbrellas left to shelter M people,
     • Return INF.
   • Declare an integer variable ANS.
   • Set ANS to minNumberOfUmbrellas(i - 1, M, UMBRELLA) i.e not considering the i-th coin.
   • If M >= UMBRELLA[i - 1],
     • Update ans to min(ans, 1 + minNumberOfUmbrellas(i - 1, M - UMBRELLA[i - 1])) i.e considering the i-th umbrella.
   • Return the ANS.

Approach: In the previous approach, there will be a lot of overlapping subproblems. Hence, we can store results of subproblems by applying memoization to the previous approach and optimize it.

The algorithm is as follows:

• Declare a 2D array DP[][] of size (N + 1) * (M + 1), where, DP[i][j] represents the minimum number of umbrellas required to shelter j people with first i umbrellas. Initially initialize the DP[][] with -1, -1 representing that the particular subproblem is not solved yet.
• Declare a minNumberOfUmbrellas function with parameters i, M, UMBRELLA, dp where i represents the index for the i-th umbrella we are taking, M is the required number of people to shelter, UMBRELLA is the array passed in the input.
  • If M == 0, If the required number of people to shelter is 0 then we don’t require any umbrellas.
    • Return 0.
  • Else If i == 0, then we don’t have any umbrellas left to shelter M people,
    • Return INF.
  • If DP[i][M] != -1, this sub-problem is solved before hence we don’t need to solve it again,
    • Return DP[i][M].
  • Declare an integer variable ANS.
  • Set ANS to minNumberOfUmbrellas(i - 1, M, UMBRELLA) i.e not considering the i-th umbrella.
  • If M >= UMBRELLA[i - 1],
    • Update ANS to min(ANS, 1 + minNumberOfUmbrellas(i - 1, M - UMBRELLA[i - 1])) i.e considering the i-th umbrella.
  • Return DP[i][M] = ANS.

Approach: The idea is to use dynamic programming to store the results of a subproblem and then use the stored results to solve other subproblems.

The algorithm is as follows:

1. Declare a 2D array DP[][] of size (N + 1) * (M + 1), where, DP[i][j] represents the minimum number of umbrellas required to shelter j people with first i umbrellas.
2. Iterate from i = 0 to N,
   • Iterate from j = 0 to N,
     • If j == 0, If the required number of people to shelter is 0 then we don’t require any umbrellas.
       • Set DP[i][j] to 0.
     • Else If i == 0, then we don’t have any umbrellas left to shelter M people,
       • Set, DP[i][j] = INF.
     • Else,
       • Set DP[i][j] to DP[i - 1][j] i.e i.e not considering the i-th umbrella.
       • If j >= UMBRELLA[i - 1],
         • Update DP[i][j] to min(DP[i][j], 1 + DP[i - 1][j - UMBRELLA[i - 1] i.e considering the i-th umbrella.
3. Declare an integer variable ANS and set it to DP[N][M] because we need to compute the minimum number of umbrellas to shelter M people with first N umbrellas.
4. If ANS >= INF,
   • Return -1.
5. Return ANS.