【C++刷题】优选算法——动态规划第六辑

2024-04-30 04:04
文章标签 算法 动态 规划 c++ 刷题 优选 第六

本文主要是介绍【C++刷题】优选算法——动态规划第六辑，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  1. 【模板】01背包
状态表示:dp1[i][j]: 表示从前i个物品中挑选总体积不超过j的物品，在所有的选法中，能挑选出的最大价值dp2[i][j]: 表示从前i个物品中挑选总体积正好等于j的物品，在所有的选法中，能挑选出的最大价值
优化:利用滚动数组做空间上的优化

int main()
{int n, V; // n 物品个数 V 背包体积cin >> n >> V;int v, w; // v 物品体积 w物品价值vector<pair<int, int>> goods(1);while(cin >> v >> w) goods.push_back(make_pair(v, w));// 1.dp数组vector<vector<int>> dp1(n + 1, vector<int>(V + 1));vector<vector<int>> dp2(n + 1, vector<int>(V + 1));// 2.初始化for(int j = 1; j < dp2[0].size(); ++j) dp2[0][j] = -1;// 3.状态转移方程for(int i = 1; i < dp1.size(); ++i){for(int j = 1; j < dp1[0].size(); ++j){if(j - goods[i].first >= 0)dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-goods[i].first] + goods[i].second);elsedp1[i][j] = dp1[i-1][j];}}for(int i = 1; i < dp2.size(); ++i){for(int j = 1; j < dp2[0].size(); ++j){if(j - goods[i].first >= 0 && dp2[i-1][j-goods[i].first] != -1)dp2[i][j] = max(dp2[i-1][j], goods[i].second + dp2[i-1][j-goods[i].first]);elsedp2[i][j] = dp2[i-1][j];}}// 4.返回值cout << dp1.back().back() << endl;cout << (dp2.back().back() == -1 ? 0 : dp2.back().back()) << endl;return 0;
}// 优化版
int main()
{int n, V; // n 物品个数 V 背包体积cin >> n >> V;int v, w; // v 物品体积 w物品价值vector<pair<int, int>> goods(1);while(cin >> v >> w) goods.push_back(make_pair(v, w));// 1.dp数组vector<int> dp1(V + 1);vector<int> dp2(V + 1);// 2.初始化for(int j = 1; j < dp2.size(); ++j) dp2[j] = -1;// 3.状态转移方程for(int i = 1; i <= n; ++i){for(int j = dp1.size() - 1; j - goods[i].first >= 0; --j){dp1[j] = max(dp1[j], dp1[j-goods[i].first] + goods[i].second);}}for(int i = 1; i <= n; ++i){for(int j = dp2.size() - 1; j - goods[i].first >= 0; --j){if(dp2[j-goods[i].first] != -1)dp2[j] = max(dp2[j], goods[i].second + dp2[j-goods[i].first]);}}// 4.返回值cout << dp1.back() << endl;cout << (dp2.back() == -1 ? 0 : dp2.back()) << endl;return 0;
}
  1. 分割等和子集
问题转化:是否能在在数组中选择一些和为num/2的数出来
状态表示:dp[i][j]: 表示从前i个数中能否选出一组数，使它的和为j

bool canPartition(vector<int>& nums)
{// 0.预处理int sum = 0;for(int e : nums) sum += e;if(sum % 2) return false;sum /= 2;// 1.dp数组vector<vector<bool>> dp(nums.size() + 1, vector<bool>(sum + 1));// 2.初始化for(int i = 0; i < dp.size(); ++i) dp[i][0] = true;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){if(j - nums[i-1] >= 0)dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];elsedp[i][j] = dp[i-1][j];}}// 4.返回值return dp.back().back();
}// 优化版
bool canPartition(vector<int>& nums)
{// 0.预处理int sum = 0;for(int e : nums) sum += e;if(sum % 2) return false;sum /= 2;// 1.dp数组vector<bool> dp(sum + 1);// 2.初始化dp[0] = true;// 3.状态转移方程for(int i = 1; i <= nums.size(); ++i){for(int j = dp.size() - 1; j - nums[i-1] >= 0; --j){dp[j] = dp[j] || dp[j-nums[i-1]];}}// 4.返回值return dp.back();
}
  1. 目标和
问题转化:假如 nums 中正数的和为 a，负数的和取绝对值为 b，则由 a-b=target; a+b=sum; 得到 a=(target+sum)/2所以问题可以转化为: 在 nums 数组中挑选一些数出来，使它的和等于 a，问一共有多少种挑选的方法
状态表示:dp[i][j]: 在 nums 数组的前 i 个数中一共有多少种挑选方式，使挑选出来的数的和等于 j

int findTargetSumWays(vector<int>& nums, int target)
{// 0.预处理int sum = 0;for(int e : nums) sum += e;int aim = (target + sum) / 2;if(aim < 0 || (target + sum) % 2) return 0;// 1.dp数组vector<vector<int>> dp(nums.size() + 1, vector<int>(aim + 1));// 2.初始化dp[0][0] = 1;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){if(j - nums[i-1] >= 0){dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];}else{dp[i][j] = dp[i-1][j];}}}// 4.返回值return dp.back().back();
}// 优化版
int findTargetSumWays(vector<int>& nums, int target)
{// 0.预处理int sum = 0;for(int e : nums) sum += e;int aim = (target + sum) / 2;if(aim < 0 || (target + sum) % 2) return 0;// 1.dp数组vector<int> dp(aim + 1);// 2.初始化dp[0] = 1;// 3.状态转移方程for(int i = 1; i <= nums.size(); ++i){for(int j = dp.size() - 1; j - nums[i-1] >= 0; --j){dp[j] += dp[j - nums[i-1]];}}// 4.返回值return dp.back();
}
  1. 最后一块石头的重量 II
问题转化:在数组中选一些数出来，使这些数的和尽可能地接近 sum/2
状态表示:dp[i][j]: 表示从数组的前 i 个元素中选一些数出来，其总和不大于 j 的最大和

int lastStoneWeightII(vector<int>& stones)
{// 0.预处理int sum = 0;for(int e : stones) sum += e;int aim = sum / 2;// 1.dp数组vector<vector<int>> dp(stones.size() + 1, vector<int>(aim + 1));// 2.初始化// 4.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){if(j - stones[i-1] >= 0){dp[i][j] = max(dp[i-1][j], dp[i-1][j - stones[i-1]] + stones[i-1]);}else{dp[i][j] = dp[i-1][j];}}}// 4.返回值return sum - 2*dp.back().back();
}// 优化版
int lastStoneWeightII(vector<int>& stones)
{// 0.预处理int sum = 0;for(int e : stones) sum += e;int aim = sum / 2;// 1.dp数组vector<int> dp(aim + 1);// 2.初始化// 4.状态转移方程for(int i = 1; i <= stones.size(); ++i){for(int j = dp.size() - 1; j - stones[i-1] >= 0; --j){dp[j] = max(dp[j], dp[j - stones[i-1]] + stones[i-1]);}}// 4.返回值return sum - 2*dp.back();
}
  1. 【模板】完全背包
状态表示:dp1[i][j]: 表示从前 i 个物品中，所选出的物品，体积不大于 j 的最大价值dp2[i][j]: 表示从前 i 个物品中，所选出的物品，体积正好等于 j 的最大价值

int main()
{// 0.预处理int n, V; // n 物品个数 V 背包体积cin >> n >> V;vector<pair<int, int>> goods(1);int v, w; // v 物品的体积 w 物品的价值while(cin >> v >> w) goods.push_back(make_pair(v, w));// 1.dp数组vector<vector<int>> dp(n + 1, vector<int>(V + 1));vector<vector<int>> dp2(n + 1, vector<int>(V + 1, -1));// 2.初始化dp2[0][0] = 0;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){dp[i][j] = dp[i-1][j];if(j - goods[i].first >= 0){dp[i][j] = max(dp[i][j], dp[i][j - goods[i].first] + goods[i].second);}// int k = 1;// while(true)// {//     if(j - k * goods[i].first >= 0)//     {//         dp[i][j] = max(dp[i][j], dp[i-1][j - k * goods[i].first] + k * goods[i].second);//         ++k;//     }//     else//     {//         break;//     }// }}}for(int i = 1; i < dp2.size(); ++i){for(int j = 0; j < dp2[0].size(); ++j){dp2[i][j] = dp2[i-1][j];if(j - goods[i].first >= 0 && dp2[i][j - goods[i].first] != -1){dp2[i][j] = max(dp2[i][j], dp2[i][j - goods[i].first] + goods[i].second);}// int k = 1;// while(true)// {//     if(j - k * goods[i].first >= 0)//     {//         if(dp2[i-1][j - k * goods[i].first] != -1)//         {//             dp2[i][j] = max(dp2[i][j], dp2[i-1][j - k * goods[i].first] + k * goods[i].second);//         }//         ++k;//     }//     else//     {//         break;//     }// }}}// 4.返回值cout << dp.back().back() << endl;cout << (dp2.back().back() == -1 ? 0 : dp2.back().back())  << endl;return 0;
}// 优化版
int main()
{// 0.预处理int n, V; // n 物品个数 V 背包体积cin >> n >> V;vector<pair<int, int>> goods(1);int v, w; // v 物品的体积 w 物品的价值while(cin >> v >> w) goods.push_back(make_pair(v, w));// 1.dp数组vector<int> dp(V + 1);vector<int> dp2(V + 1, -1);// 2.初始化dp2[0] = 0;// 3.状态转移方程for(int i = 1; i < goods.size(); ++i){for(int j = goods[i].first; j < dp.size(); ++j){dp[j] = max(dp[j], dp[j - goods[i].first] + goods[i].second);}// for(int j = 0; j < dp.size(); ++j)// {//     if(j - goods[i].first >= 0)//     {//         dp[j] = max(dp[j], dp[j - goods[i].first] + goods[i].second);//     }// }}for(int i = 1; i < goods.size(); ++i){for(int j = goods[i].first; j < dp2.size(); ++j){if(dp2[j - goods[i].first] != -1){dp2[j] = max(dp2[j], dp2[j - goods[i].first] + goods[i].second);}}// for(int j = 0; j < dp2.size(); ++j)// {//     if(j - goods[i].first >= 0 && dp2[j - goods[i].first] != -1)//     {//         dp2[j] = max(dp2[j], dp2[j - goods[i].first] + goods[i].second);//     }// }}// 4.返回值cout << dp.back() << endl;cout << (dp2.back() == -1 ? 0 : dp2.back())  << endl;return 0;
}
  1. 零钱兑换
状态表示:dp[i][j]: 表示从前 i 种硬币中，在所有取出的硬币总额等于 j 的方式中，所取出的最少硬币数

int coinChange(vector<int>& coins, int amount)
{// 1.dp数组vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, -1));// 2.初始化dp[0][0] = 0;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){                dp[i][j] = dp[i-1][j];if(j - coins[i-1] >= 0 && dp[i][j - coins[i-1]] != -1){if(dp[i][j] != -1) dp[i][j] = min(dp[i][j], dp[i][j - coins[i-1]] + 1);else dp[i][j] = dp[i][j - coins[i-1]] + 1;}}}// 4.返回值return dp.back().back();
}// 优化版
int coinChange(vector<int>& coins, int amount)
{// 1.dp数组vector<int> dp(amount + 1, -1);// 2.初始化dp[0] = 0;// 3.状态转移方程for(int i = 1; i <= coins.size(); ++i){for(int j = 0; j < dp.size(); ++j){                if(j - coins[i-1] >= 0 && dp[j - coins[i-1]] != -1){if(dp[j] != -1) dp[j] = min(dp[j], dp[j - coins[i-1]] + 1);else dp[j] = dp[j - coins[i-1]] + 1;}}}// 4.返回值return dp.back();
}
  1. 零钱兑换 II
状态表示:dp[i][j]: 表示从 i 种硬币中，可以挑选出总额等于 j 的不同挑选方式

int change(int amount, vector<int>& coins)
{// 1.dp数组vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1));// 2.初始化dp[0][0] = 1;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){dp[i][j] = dp[i-1][j];if(j - coins[i-1] >= 0){dp[i][j] += dp[i][j-coins[i-1]];}}}// 4.返回值return dp.back().back();
}// 优化版
int change(int amount, vector<int>& coins)
{// 1.dp数组vector<int> dp(amount + 1);// 2.初始化dp[0] = 1;// 3.状态转移方程for(int i = 1; i <= coins.size(); ++i){for(int j = coins[i-1]; j < dp.size(); ++j){dp[j] += dp[j-coins[i-1]];}}// 4.返回值return dp.back();
}
  1. 完全平方数
状态表示:dp[i][j]: 表示从前 i 种完全平方数中，能挑选出总和等于 j 的所有方式中，挑选的完全平方数最少的个数

int numSquares(int n)
{// 0.预处理int m = sqrt(n);// 1.dp数组vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));// 2.初始化dp[0][0] = 0;// 3.状态转移方程for(int i = 1; i < dp.size(); ++i){for(int j = 0; j < dp[0].size(); ++j){dp[i][j] = dp[i-1][j];if(j - pow(i, 2) >= 0 && dp[i][j - pow(i, 2)] != -1){if(dp[i][j] != -1){dp[i][j] = min(dp[i][j], dp[i][j - pow(i, 2)] + 1);}else{dp[i][j] = dp[i][j - pow(i, 2)] + 1;}}}}// 4.返回值return dp.back().back();
}// 优化版
int numSquares(int n)
{// 0.预处理int m = sqrt(n);// 1.dp数组vector<int> dp(n + 1, -1);// 2.初始化dp[0] = 0;// 3.状态转移方程for(int i = 1; i <= m; ++i){for(int j = pow(i, 2); j < dp.size(); ++j){if(dp[j - pow(i, 2)] != -1){if(dp[j] != -1) dp[j] = min(dp[j], dp[j - pow(i, 2)] + 1);else dp[j] = dp[j - pow(i, 2)] + 1;}}}// 4.返回值return dp.back();
}
  1. 一和零
状态表示:dp[i][j][k]: 表示从前i个二进制字符串中，能选出的字符'0'的个数不大于j，字符'1'的个数不大于k的所有方式中，二进制字符串最多的个数

int findMaxForm(vector<string>& strs, int m, int n)
{// 1.dp数组vector<vector<vector<int>>> dp(strs.size() + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));// 2.初始化// 3.状态转移方程for(int i = 1; i <= strs.size(); ++i){int c0 = 0, c1 = 0;for(char c : strs[i-1]){if(c == '0') ++c0;else ++c1;}for(int j = 0; j <= m; ++j){for(int k = 0; k <= n; ++k){dp[i][j][k] = dp[i-1][j][k];if(j - c0 >= 0 && k - c1 >= 0){dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-c0][k-c1] + 1);}}}}// 4.返回值return dp[strs.size()][m][n];
}// 优化版
int findMaxForm(vector<string>& strs, int m, int n)
{// 1.dp数组vector<vector<int>> dp(m + 1, vector<int>(n + 1));// 2.初始化// 3.状态转移方程for(int i = 1; i <= strs.size(); ++i){int c0 = 0, c1 = 0;for(char c : strs[i-1]){if(c == '0') ++c0;else ++c1;}for(int j = m; j - c0 >= 0; --j){for(int k = n; k - c1 >= 0; --k){dp[j][k] = max(dp[j][k], dp[j-c0][k-c1] + 1);}}}// 4.返回值return dp[m][n];
}
  1. 盈利计划
状态表示:dp[i][j][k]: 表示从前 i 个工作中挑选，总人数小于等于 j，总利润大于等于 k 的所有选择方式

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
{const int MOD = 1e9+7;// 1.dp数组vector<vector<vector<int>>> dp(group.size() + 1, vector<vector<int>>(n+1, vector<int>(minProfit+1)));// 2.初始化for(int j = 0; j <= n; ++j){dp[0][j][0] = 1;}// 3.状态转移方程for(int i = 1; i <= group.size(); ++i){for(int j = 0; j <= n; ++j){for(int k = 0; k <= minProfit; ++k){dp[i][j][k] = dp[i-1][j][k];if(j - group[i-1] >= 0){dp[i][j][k] += dp[i-1][j-group[i-1]][max(0, k-profit[i-1])];}dp[i][j][k] %= MOD;}}}// 4.返回值return dp.back().back().back();
}// 优化版
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit)
{const int MOD = 1e9+7;// 1.dp数组vector<vector<int>> dp(n+1, vector<int>(minProfit+1));// 2.初始化for(int j = 0; j <= n; ++j){dp[j][0] = 1;}// 3.状态转移方程for(int i = 1; i <= group.size(); ++i){for(int j = n; j - group[i-1] >= 0; --j){for(int k = 0; k <= minProfit; ++k){dp[j][k] += dp[j-group[i-1]][max(0, k-profit[i-1])];dp[j][k] %= MOD;}}}// 4.返回值return dp.back().back();
}
  1. 组合总和 Ⅳ
背包问题：有限制条件下的“组合”问题根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
状态表示:dp[i]: 表示凑成总和 i，一共有多少种排列数

int combinationSum4(vector<int>& nums, int target)
{// 1.dp数组vector<double> dp(target + 1);// 2.初始化dp[0] = 1;// 3.状态转移方程for(int i = 1; i <= target; ++i){for(int num : nums){if(i - num >= 0) dp[i] += dp[i-num];}}// 4.返回值return dp.back();
}
  1. 不同的二叉搜索树
根据分析问题的过程中，发现重复子问题，抽象出来一个状态表示
状态表示:dp[i]: 表示节点个数为 i 的时候，一共有多少种二叉搜索树

int numTrees(int n)
{// 1.dp数组vector<int> dp(n + 1);// 2.初始化dp[0] = 1;// 3.状态转移方程for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j){dp[i] += dp[j-1] * dp[i-j];}}// 4.返回值return dp.back();
}

这篇关于【C++刷题】优选算法——动态规划第六辑的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/947862。

相关文章

使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
使用C++实现单链表的操作与实践

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...
Java使用POI-TL和JFreeChart动态生成Word报告

Java使用POI-TL和JFreeChart动态生成Word报告

《Java使用POI-TL和JFreeChart动态生成Word报告》本文介绍了使用POI-TL和JFreeChart生成包含动态数据和图表的Word报告的方法,并分享了实际开发中的踩坑经验,通过代码... 目录前言一、需求背景二、方案分析三、 POI-TL + JFreeChart 实现3.1 Maven
阅读更多...
Java导出Excel动态表头的示例详解

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法，代码不进
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2