首页 > 试题广场 >

生产口罩

[编程题]生产口罩

热度指数：1607 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹是一家口罩厂家的老板，由于现在疫情严重，牛妹想重新分配每条生产线上的人数来使得能生产的口罩最多。

牛妹所在的公司一共有 $m$ 名员工， $n$ 条生产线(0.....n-1)，每条生产线有strategy[i].size种人数安排策略。例如： $3$ 个人在 $a$ 生产线上， $a$ 生产线每天生产 $8$ 个口罩； $5$ 个人在 $a$ 生产线上，每天 $a$ 生产线能生产 $15$ 个口罩。
牛妹想知道通过合理的策略安排最多每天能生产多少口罩？（可以不用将所有员工都分配上岗，生产线可以选择闲置）

示例1

输入

3,5,[[(1,3),(2,4)],[(3,4),(4,4)],[(8,8)]]

输出

说明

样例解释： 号生产线采用策略，号生产线采用策略，号生产线不生产

备注:


strategy[i][j].x表示人数，strategy[i][j].y表示能生产的口罩数

算法知识视频讲解

C/C++

nbgao

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

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) {
        int dp1[m+1], dp2[m+1];
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));
        for(int i=1;i<=n;i++){
            vector<Point> s = strategy[i-1];
            for(auto &p: s)
                for(int j=0;j+p.x<=m;j++)
                    dp2[j+p.x] = max(dp2[j+p.x], dp1[j]+p.y);
            for(int j=0;j<=m;j++)
                dp1[j] = dp2[j];
        }
        return dp2[m];
    }
};

发表于 2020-08-14 18:21:41 回复(0)

杭电5餐厨师长

理解成01背包问题。只不过这次不是把商品的选择策略不再是0或者1。而是有多种情况。

dp[i][j]表示，前i个工厂线，一共有j个人，他的选择策略。转移方程。dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost]+val)枚举第i个生产线的每一个cost和val。也就是需要的人数和产能。

新写的更容易理解的java代码。

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) {
        // write code here
        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 p :strategy[i-1]){
                    if(j < p.x) continue;
                    dp[i][j] = Math.max(dp[i-1][j-p.x]+p.y,dp[i][j]);
                }
            }
        }
        return dp[n][m];
    }
}

发表于 2020-03-13 15:59:33 回复(0)

一只老风铃

采取逆序填充的滚动数组，可以达到空间复杂度最低。

 
int producemask(int n, int m, vector<vector<Point> >& strategy) {
        // write code here
        vector<int> dp(m+1,0);
        for(int i=0;i<n;i++)  //每一轮分析投入新的生产线与否能否增加生产数
        {
            for(int j=m;j>0;j--)  //这里由于是01背包问题，滚动数组采取m=>0  逆序填充 
            {
                //研究每条生产线 上各种方案
                for(int k=0;k<strategy[i].size();k++)
                {
                    int x=strategy[i][k].x;//人数开销
                    int y=strategy[i][k].y;//口罩数
                    if(j>=x)  //若当前人数能够超过要求
                    {  
                        dp[j]=max(dp[j],dp[j-x]+y);  //取一个较大值   
                    }     
                }
            }  
        }
        return dp[m];//最后dp[m]即为所求
    }

编辑于 2020-10-05 10:48:54 回复(0)