题解 | #生产口罩#

题目描述
牛妹是一家口罩厂家的老板，由于现在疫情严重，牛妹想重新分配每条生产线上的人数来使得能生产的口罩最多。
牛妹所在的公司一共有m名员工，n条生产线(0.....n-1)，每条生产线有strategy[i].size种人数安排策略。例如：3个人在a生产线上，a生产线每天生产8个口罩；5个人在a生产线上，每天a生产线能生产15个口罩。
牛妹想知道通过合理的策略安排最多每天能生产多少口罩？（可以不用将所有员工都分配上岗，生产线可以选择闲置）

方法一：动态规划解法

求解思路
对于求解本题如何合理的安排生产线使得每天生产的口罩最多，我们想到使用动态规划的思想来解决本题目。我们定义dp[i][j]为第i条生产线上j名员工每天生产多少口罩。自然初始条件中每条生产线上0名员工生产的口罩为0，dp[i][0]=0.同时我们考虑到每增加一条生产线，都有两种选择。第一种是选择闲置，第二种则是在对应策略数组中选择一个最佳策略。对于第一种情况，有dp[i][j]=dp[i-1][j].对于第二种情况则有dp[i][j]=max{dp[i][j],dp[i-1][j-strategy.x]+strategy.y}

图片说明

解题代码

import java.util.*;
public class Solution {
    public int producemask (int n, int m, Point[][] strategy) {
        int[][] mydp=new int[n+1][m+1]; // 定义mydp数组，mydp[i][j]表示i条生产线，j名员工每天产多少口罩
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {   //默认当前生产线闲置
                mydp[i][j]=mydp[i-1][j]; // 第一种情况
                //如果不闲置，则从所有策略种，选出一种最佳分配
                for(Point s:strategy[i-1])
                {   //要求当前员工数大于等于策略需要的员工
                    if(j>=s.x)
                    {
                        mydp[i][j]=Math.max(mydp[i][j],mydp[i-1][j-s.x]+s.y); // 第二种情况
                    }
                }
            }
        }
        return mydp[n][m]; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环加一层常数级循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用辅助数组dp[n][n]，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：基于动态规划的优化求解

求解思路
我们在基于方法一的思路上发现对于增加的生产线，当前总共生产的口罩数只和未增加这条生产线时的状态有关，并且当前状态的计算只与前面的状态有关，所以我们只需要从后往前遍历，按照上述的思路即可得到本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int producemask (int n, int m, Point[][] strategy) {
        int[] mydp=new int[m+1]; //定义mydp数组,mydp[i]表示i个人每天最多生产多少口罩
        for(int i=1;i<=n;i++)
        {   //从前往后，之前算过的状态会叠加，所以倒序访问
            for(int j=m;j>=1;j--)
            {   //枚举当前生产线的所有策略
                for(Point s:strategy[i-1])
                {   //如果当前人数大于策略分配人数，则比较哪个策略最优
                    if(j>=s.x)
                    {
                        mydp[j]=Math.max(mydp[j],mydp[j-s.x]+s.y); // 状态转移
                    }
                }
            }
        }
        return mydp[m]; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环加一层常数级循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：引入辅助数组dp[n]，因此空间复杂度为 $O(N)$