题解 | #生产口罩#

题意整理

• 牛妹要安排m名员工到n条生产线生产口罩。
• 每条生产线有一个策略数组，对于这条生产线，牛妹要么一个员工也不给安排，要么按策略数组的某条策略进行安排。
• 求怎么样安排每天生产的口罩最多，最多是多少。

方法一（动态规划）

1.解题思路

• 状态定义： 表示i条生产线，j名员工每天产多少口罩。
• 状态初始化：所有状态值初始化为0。
• 状态转移：每增加一条生产线，当前增加的生产线有两种选择，一种是选择闲置，另一种是在对应策略数组选择一个最佳策略。如果选择闲置，则相较于之前没有变化，即 ;如果选择某种策略，则需要当前人手大于等于策略需要人手，如果满足，则从所有选择中挑出一种产能最高的，即 。

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类二维数组 策略
     * @return int整型
     */
    public int producemask (int n, int m, Point[][] strategy) {
        //定义dp数组，dp[i][j]表示i条生产线，j名员工每天产多少口罩
        int[][] dp=new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //默认当前生产线闲置
                dp[i][j]=dp[i-1][j];
                //如果不闲置，则从所有策略种，选出一种最佳分配
                for(Point s:strategy[i-1]){
                    //要求当前员工数大于等于策略需要的员工
                    if(j>=s.x){
                        dp[i][j]=Math.max(dp[i][j],dp[i-1][j-s.x]+s.y);
                    }
                }
            }
        }
        return dp[n][m];
    }
}

3.复杂度分析

• 时间复杂度：总共三层循环，需要执行 次， 是一个常数，所以时间复杂度是 。
• 空间复杂度：需要额外大小为 的dp数组，所以空间复杂度为 。

方法二（动态规划+状态压缩）

1.解题思路

• 基本思路和方法一相同。由于每增加一条生产线，当前总共生产的口罩数只与未增加这条生产线时的状态有关，所以可以采用滚动数组的方式，将生产线的维度去掉。
• 当前的状态计算依赖于前面的状态，所以需要从后往前遍历，避免状态的重复计算。

动图展示：

2.代码实现

import java.util.*;

/*
 * public class Point {
 *   int x;
 *   int y;
 *   public Point(int x, int y) {
 *     this.x = x;
 *     this.y = y;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类二维数组 策略
     * @return int整型
     */
    public int producemask (int n, int m, Point[][] strategy) {
        //定义dp数组,dp[i]表示i个人每天最多生产多少口罩
        int[] dp=new int[m+1];

        for(int i=1;i<=n;i++){
            //从前往后，之前算过的状态会叠加，所以倒序访问
            for(int j=m;j>=1;j--){
                //枚举当前生产线的所有策略
                for(Point s:strategy[i-1]){
                    //如果当前人数大于策略分配人数，则比较哪个策略最优
                    if(j>=s.x){
                        dp[j]=Math.max(dp[j],dp[j-s.x]+s.y);
                    }
                }
            }
        }
        return dp[m];
    }
}

3.复杂度分析

• 时间复杂度：总共三层循环，需要执行 次， 是一个常数，所以时间复杂度是 。
• 空间复杂度：需要额外大小为m+1的dp数组，所以空间复杂度为 。