01背包是经典的动态规划，其研究每一个背包是否加入到解中，即：

dp[k][n]  表示分析到第k个背包时，若有n容量能获取的最大价值 dp[k][n]=max(dp[k-1][n],dp[k-1][n-cost]+value)

01背包由于每一次只会使用到k-1的结果，可以考虑采取滚动数组进行空间优化

dp[n]=max(dp[n],dp[n-cost]+value) 注意n逆序方式从最大值向=>1 进行迭代计算

每一轮分析第k个背包，那么已有的dp数组存放的是第k-1轮计算结果

采取逆序填充，确保dp[n-cost]为上一轮结果，因为每一个背包最多取一次。

 

题目描述

生产口罩

时间限制 :1sec / 空间限制: 256MB

题意：

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

输入：

 

给定n,mn,m，strategystrategy数组

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

输出：

返回每天最大的口罩生产数量

 

示例1

输入

复制

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

输出

复制

8

 

 

思路：

分类01背包问题，指的是将背包分成几大类，每次只能在一大类中最多取一个。那么解决思路为：

每一轮研究一大类，分析每一大类中的最大值。采取逆序滚动数组降低空间开销。

 

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]即为所求 }