Monsoon Umbrella Problem in Java

The Monsoon Umbrella problem is a classic Java programming problem used to test the skills of a programmer. The problem involves writing a program to determine the number of umbrellas a person needs to buy to stay dry during a monsoon season. It is a problem that requires a programmer to compute the minimum number of umbrellas needed to cover a given set of people during a monsoon season. The program must then output the total number of umbrellas the person needs to buy to stay dry throughout the season.

Case 1:

In this problem, several people will be given. Based on the size of the umbrellas, we need to find the minimum number required to cover the given number of people. The size of the umbrella indicates the maximum number of people an umbrella can cover. If the size of an umbrella is 2, then it indicates it can cover a maximum of 2 people.

Example

Input: Number of people = 10

Size of umbrella =2

Output: Minimum number of Umbrellas required: 5

File Name: MonsoonUmbrella.java

// Importing required packages
import java. util.*;
// public class declaration
public class MonsoonUmbrella
{
    // Main section of the program where the execution of the program begins
	public static void main(String[] args) {
	    // creating object for scanner class
	    Scanner sc=new Scanner(System.in);
	    // Enter the number of people
	    System. out.println("Enter number of people");
	    int n=sc.nextInt();
	    // Enter umbrella size
	    System. out.println("Enter the  umbrella size");
	    int us=sc.nextInt();
	    // Printing the Minimum number of umbrellas required
	    System. out.println("The Minimum number of umbrellas required is "+(n/us));
		
	}
}

Output:

Enter the number of people
10
Enter umbrella size
2
The minimum number of umbrellas required is 5

Case 2

Several umbrellas, ‘N’, of different sizes will be given. We need to find the minimum number of umbrellas required to cover the ‘K’ number of people. If there is no combination of umbrellas to cover, return -1.

Input Format

The First Line’s first value is the number of umbrellas array size(N), and the second integer is the number of people (K)

The second line contains all the different sizes of umbrellas.

Input

3 30

[5 10 25]

Output: 2

Explanation

One umbrella can hold 25 people, and the other can hold 5.

Using Dynamic Programming

The goal is to solve one subproblem first, then use the solutions from that subproblem to solve other subproblems using dynamic programming.

Algorithm

• Create a 2D array of size (N + 1) * (M + 1) called DP[][], where DP[i][j] is the bare minimum number of umbrellas needed to cover j individuals with the first I umbrellas.
• Iterate from I = 0 to N, j = 0 to N, etc.
• If j == 0, no umbrellas are needed because no persons need to seek cover.
• Placing DP[i][j] at 0.
• Else, We no longer have enough umbrellas to cover M individuals if I == 0.
• DP[i][j] = INF is set.
• Else, Set DP[i][j] to DP[i - 1][j], i.e., stop considering the i-th umbrella.
• Update DP[i][j] to min(DP[i][j], 1 + DP[i - 1][j - UMBRELLA[i - 1] i.e. taking into account the i-th umbrella if j >= UMBRELLA[i - 1].
• Because we must determine the bare minimum of umbrellas necessary to cover M persons with the first N umbrellas, we must declare an integer variable ANS and set it to DP[N][M].
• Return ANS if ANS >= INF; otherwise, return -1.

File Name: MinimumUmbrellaRequired.java

public class MinimumUmbrellaRequired {
    public static void main(String s[])
    {
        int umbrella[]={5,10,25};
        int m=30;
        int ans=minNumberUmbrellas(umbrella,m);
        System.out.println(ans);
    }
    public static int minNumberUmbrellas(int[] umbrella, int m)  {
        int n = umbrella.length, inf = (int)1e9 + 5;


        int[][] dp = new int[n + 1][m + 1];


        for (int i = 0; i <= umbrella.length; i++) {
            for (int j = 0; j <= m; j++) {


                if (j == 0) {
                    dp[i][j] = 0;
                }


                else if (i == 0) {
                    dp[i][j] = inf;
                } else {
                    dp[i][j] = dp[i - 1][j];


                    if (j >= umbrella[i - 1]) {
                        dp[i][j] = Math.min(dp[i][j], 1 + dp[i - 1][j - umbrella[i - 1]]);
                    }


                }


            }
        }


        int ans = dp[n][m];


        if (ans >= inf) {
            return -1;
        }


        return ans;
    }
}

Output

2

Complexity Analysis

Time Complexity

Time Complexity is O(N * M), where N is the variety of umbrellas available and M is the number of persons who will need to use umbrellas to protect themselves.

Space Complexity

As we are utilizing a 2D auxiliary array of order N * M. The total complexity of the space is O(N * M).