Monsoon Umbrella Problem in Java

季风雨伞问题是一个经典的 Java 编程问题，用于测试程序员的技能。该问题涉及编写一个程序，以确定一个人在季风季节需要购买多少把雨伞才能保持干燥。

问题陈述

这是一个需要程序员计算在季风季节覆盖一组给定人员所需的最小雨伞数量的问题。然后，程序必须输出一个人在整个季节保持干燥所需的雨伞总数。

情况 1

在这个问题中，会给出几个人。根据雨伞的大小，我们需要找到覆盖给定人数所需的最小数量。雨伞的大小表示一把雨伞最多可覆盖的人数。如果雨伞的大小是 2，则表示它最多可以覆盖 2 个人。

示例

输入：人数 = 10

雨伞大小 =2

输出：所需最少雨伞数量：5

文件名：MonsoonUmbrella.java

输出

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

情况 2

将给出若干把不同尺寸的雨伞 'N'。我们需要找到覆盖 'K' 人所需的最小雨伞数量。如果没有雨伞组合可以覆盖，则返回 -1。

输入格式

第一行的第一个值是雨伞的数量 数组 大小 (N)，第二个整数是人数 (K)

第二行包含所有不同的雨伞尺寸。

输入

3 30

[5 10 25]

输出 2

解释

一把雨伞可以容纳 25 人，另一把可以容纳 5 人。

使用动态规划

目标是先解决一个子问题，然后使用该子问题的解决方案通过 动态规划 来解决其他子问题。

算法

1. 创建一个大小为 (N + 1) * (M + 1) 的 二维数组，称为 DP[][]，其中 DP[i][j] 是使用前 I 把雨伞覆盖 j 个人所需的最低雨伞数量。
2. 从 I = 0 到 N，j = 0 到 N 等进行迭代。
3. 如果 j == 0，则不需要雨伞，因为没有人需要遮蔽。
4. 将 DP[i][j] 设置为 0。
5. 否则，如果我们没有足够的雨伞来覆盖 M 个人，则 I == 0。
6. DP[i][j] 设置为 INF。
7. 否则，将 DP[i][j] 设置为 DP[i - 1][j]，即不考虑第 i 把雨伞。
8. 如果 j >= UMBRELLA[i - 1]，则将 DP[i][j] 更新为 min(DP[i][j], 1 + DP[i - 1][j - UMBRELLA[i - 1])，即考虑第 i 把雨伞。
9. 由于我们必须确定使用前 N 把雨伞覆盖 M 个人的最少所需雨伞数量，因此我们必须声明一个整数变量 ANS 并将其设置为 DP[N][M]。
10. 如果 ANS >= INF，则返回 ANS；否则，返回 -1。

输出

 
2   

复杂度分析

时间复杂度

时间复杂度为 O(N * M)，其中 N 是可用的雨伞种类，M 是需要使用雨伞遮蔽的人数。

空间复杂度

由于我们使用了 N * M 阶的二维辅助数组，因此空间复杂度为 O(N * M)。