题解 | #生产口罩#

一.题目描述
NC519生产口罩
牛妹是一家口罩厂家的老板，由于现在疫情严重，牛妹想重新分配每条生产线上的人数来使得能生产的口罩最多。
牛妹所在的公司一共有m名员工，n条生产线(0,1,...,n-1)，每条生产线有strategy[i].size种人数安排策略。例如：3个人在a生产线上，a生产线每天生产8个口罩；5个人在a生产线上，每天a生产线能生产15个口罩。牛妹想知道通过合理的策略安排最多每天能生产多少口罩？（可以不用将所有员工都分配上岗，生产线可以选择闲置）
二.算法(动态规划)
题目可以看成类似01背包的动态规划，一旦接受了这种想法我们就可以利用动态规划的思路进行分析：
(1)状态定义：表示i条生产线，j名员工每天产多少口罩。
(2)状态初始化：全部是0
(3)状态转移：对于当前增加的生产线有两种选择，一种是选择闲置，另一种是在对应策略数组选择一个最佳策略。如果选择闲置，则相较于之前没有变化，即dp[i][j]=dp[i-1][j];如果选择某种策略，则需要当前人手大于等于策略需要人手，如果满足，则从所有选择中挑出一种产能最高的，即。
下面是完整代码：

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        int dp[n+5][m+5];
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //初始化当前生产线闲置的
                dp[i][j]=dp[i-1][j];;
                //对每一生产线进行遍历
                for(auto x:strategy[i-1]){
                    if(j>=x.x) {
                        //状态转移
                         dp[i][j]=max(dp[i][j],dp[i-1][j-x.x]+x.y);
                    }
                }
            }
        }
        return dp[n][m];
    }
};

时间复杂度：,需要要执行三次循环，k是策略的方案数，是个常数，所以复杂度是
空间复杂度：需要额外大小为的dp数组，所以空间复杂度为。
优越点：思路简单且便于理解，但是空间复杂度高。
三.算法(动态规划+状态压缩)
对于每增加一条生产线，当前总共生产的口罩数只与未增加这条生产线时的状态有关，所以可以采用滚动数组的方式状态压缩，将生产线的维度去掉。当前的状态计算只是依赖于前面的状态，所以需要从后往前遍历，避免状态的重复计算。


图片来自牛客
下面给出完整代码：

 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        int dp[m+5];//只需要用一维数组
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            for(int j=m;j>=1;j--){
                for(auto x:strategy[i-1]){
                    if(j>=x.x) {
                         dp[j]=max(dp[j],dp[j-x.x]+x.y);
                    }
                }
            }
        }
        return dp[m];
    }
};

时间复杂度：,需要要执行三次循环，是策略的方案数，是个常数，所以复杂度是
空间复杂度：需要额外大小为m的dp数组，所以空间复杂度为。
优越点：需要进一步理解，但是空间复杂度低。