[Algorithm][动态规划][二维费用的背包问题][一和零][盈利计划]详细讲解

本文主要是介绍[Algorithm][动态规划][二维费用的背包问题][一和零][盈利计划]详细讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

0.原理讲解

本质仍然是背包问题，但是相较于普通的背包问题，只是限制条件多了一个而已

1.一和零

1.题目链接

一和零

2.算法原理详解

思路：
- 确定状态表示 -> dp[i][j]的含义
  - dp[i][j][k]：从前i个字符串中挑选，字符0的个数不超过j，字符1的个数不超过k，所有的选法中，最大的长度
- 推导状态转移方程：根据最后一个位置的情况，分情况讨论
- 初始化：
  - 三个维度都多开一“行”虚拟结点
  - j, k这两个维度的初始化都可以交给DP阶段
- 确定填表顺序：i从小到大
- 确定返回值：dp[len][n][m]
滚动数组优化空间
- 大致思路与完全背包一致
- 操作
  - 删除所有的i
  - 修改一下j, k的遍历顺序
- 注意：不要去强行解释优化后的妆台表示以及状态转移方程，费时费力还没啥意义

3.代码实现

// v1.0
int findMaxForm(vector<string>& strs, int n, int m) 
{int len = strs.size();vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));for(int i = 1; i <= len; i++){// 先统计字符串中0 1的个数int a = 0, b = 0;for(auto& ch : strs[i - 1]){ch == '0' ? a++ : b++;}// DPfor(int j = 0; j <= n; j++){for(int k = 0; k <= m; k++){dp[i][j][k] = dp[i - 1][j][k];if(j >= a && k >= b){dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);}}}}return dp[len][n][m];
}
---------------------------------------------------------------------------------
// v2.0 滚动数组优化
int findMaxForm(vector<string>& strs, int n, int m) 
{int len = strs.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 1; i <= len; i++){// 先统计字符串中0 1的个数int a = 0, b = 0;for(auto& ch : strs[i - 1]){ch == '0' ? a++ : b++;}// DPfor(int j = n; j >= a; j--){for(int k = m; k >= b; k--){dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);}}}return dp[n][m];
}

2.盈利计划

1.题目链接

盈利计划

2.算法原理详解

思路：
- 确定状态表示 -> dp[i][j]的含义
  - dp[i][j][k]：从前i个计划中挑选，总人数不超过j，总利润至少为k，一共有多少种选法
- 推导状态转移方程：根据最后一个位置的情况，分情况讨论
- 初始化：
  - 三个维度都多开一“行”虚拟结点
  - dp[0][j][0] = 1
  - k这个维度的初始化可以交给DP阶段
- 确定填表顺序：i从小到大
- 确定返回值：dp[len][n][m]
滚动数组优化空间
- 大致思路与完全背包一致
- 操作
  - 删除所有的i
  - 修改一下j, k的遍历顺序
- 注意：不要去强行解释优化后的妆台表示以及状态转移方程，费时费力还没啥意义

3.代码实现

// v1.0
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
{const int MOD = 1e9 + 7;int len = g.size();// Initvector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(m + 1)));for(int j = 0; j <= n; j++){dp[0][j][0] = 1;}// DPfor(int i = 1; i <= len; i++){for(int j = 0; j <= n; j++){for(int k = 0; k <= m; k++){dp[i][j][k] = dp[i - 1][j][k];if(j >= g[i - 1]){dp[i][j][k] += dp[i - 1][j - g[i - 1]][max(0, k - p[i - 1])];}dp[i][j][k] %= MOD;}}}return dp[len][n][m];
}
------------------------------------------------------------------------------
// v2.0 滚动数组优化
int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
{const int MOD = 1e9 + 7;int len = g.size();// Initvector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int j = 0; j <= n; j++){dp[j][0] = 1;}// DPfor(int i = 1; i <= len; i++){for(int j = n; j >= g[i - 1]; j--){for(int k = m; k >= 0; k--){dp[j][k] += dp[j - g[i - 1]][max(0, k - p[i - 1])];dp[j][k] %= MOD;}}}return dp[n][m];
}