题目描述

牛妹所在的公司一共有名员工，条生产线，每条生产线有种人数安排策略.
例如：个人在生产线上，生产线每天生产个口罩；个人在生产线上，每天生产线能生产个口罩。
牛妹想知道通过合理的策略安排最多每天能生产多少口罩？
可以不用将所有员工都分配上岗，生产线可以选择闲置

方法一 动态规划

解题思路

这个问题可以用动态规划解决.定义状态数组,表示生产策略不变情况下,条生产线,名员工每天最多生产口罩数量.
初始状态:.
状态转移:需要得到与之间的关系.生产线增加一条,如果不使用新增的生产线时生产口罩最快,那么;如果使用新增的这条生产线,那么对于新增这条生产线的所有,需要找出生产最快的方案,即.最后,为这两种情况中较大的值.

代码示例

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类vector<vector<>> 策略
     * @return int整型
     */
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        // 状态数组f[i][j]:生产策略不变情况下,i条生产线,j名员工每天最多生产口罩数量
        // 初始状态为0
        int f[2003][2003] = {0};
        // 根据状态转移方程更新状态数组
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                // 如果不使用新的生产线
                f[i][j] = f[i-1][j];
                // 如果使用新的生产线,找到生产数量最大的方案
                for(int k = 0; k < strategy[i-1].size(); k++) {
                    // 保证选择的方案人数足够,也保证数组不会越界
                    if(j >= strategy[i-1][k].x) {
                        f[i][j] = max(f[i-1][j - strategy[i-1][k].x]+strategy[i-1][k].y, f[i][j]);
                    }
                }
            }
        }
        return f[n][m];
    }
};

复杂度分析

  • 时间复杂度：需要对每个生产线数量,每个人的数量进行遍历以更新状态数组,每次更新时需要遍历新生产线的所有方案,所以时间复杂度为
  • 空间复杂度：状态数组大小为,故空间复杂度为

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

解题思路

方法一中的状态转移方程为:,可以看出,只与相关,所以可以进行状态压缩,将状态数组的第维省略.
状态压缩的主要目的就是减少空间复杂度,如下图所示,压缩前的状态数组需要两维,经过压缩之后只需要一维数据进行迭代,同样能得到答案.

图片说明

定义为状态压缩之后的数组,根据之前的状态转移方程,可以看出更新需要的中的,所以在状态压缩之后的状态更新中,要逆序更新.

代码示例

/**
 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param strategy Point类vector<vector<>> 策略
     * @return int整型
     */
    int producemask(int n, int m, vector<vector<Point> >& strategy) {
        // 状态数组f[j]:生产策略不变情况下,j名员工每天最多生产口罩数量,每迭代一次新考虑一条生产线
        // 初始状态为0
        int f[2003] = {0};
        // 根据状态转移方程更新状态数组,每迭代一次新考虑一条生产线
        for(int i = 1; i <= n; i++) {
            // 因为题解中提到的原因,需要逆序更新
            for(int j = m; j >= 1; j--) {
                // 遍历新生产线的所有方案
                for(int k = 0; k < strategy[i-1].size(); k++) {
                    // 保证选择的方案人数足够,也保证数组不会越界
                    if(j >= strategy[i-1][k].x) {
                        f[j] = max(f[j - strategy[i-1][k].x]+strategy[i-1][k].y, f[j]);
                    }
                }
            }
        }
        // 考虑所有的生产线之后的最大数量
        return f[m];
    }
};

复杂度分析

  • 时间复杂度：需要对每个生产线数量,每个人的数量进行遍历以更新状态数组,每次更新时需要遍历新生产线的所有方案,所以时间复杂度为
  • 空间复杂度：经过状态压缩,状态数组大小为,所以空间复杂度为