【C++动态规划 贪心】3180. 执行操作可获得的最大总奖励 I|1848
本文涉及知识点
LeetCode3180. 执行操作可获得的最大总奖励 I
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。
以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1：
输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
示例 2：
输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
提示：
1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000
排序+动态规划+贪心之临项交换
我们令最优解按顺序选择的奖励为：{i1,i2 ⋯ \cdots ⋯ im}，则一定是升序。如果不是，则选择非升序的相邻两项交换之，仍然是解。
我3180简称奖励数组为num，对num排序。M = num.back()
动态规划的状态表示
dp[i][m] 从num的前i个元素选择奖励，最大奖励能否是m。m ∈ \in ∈[0,2M]。
动态规划的转移方程
枚举前置状态(i,m)
dp[i+1] = dp[i] 不选择第i项奖励。
如果nums[i] >m 则，dp[i+1][m+nums[i]] ||= dp[i][m]。
动态规划的填报顺序
i从0到n-1,m从0到2M。
动态规划的初始值
dp[0][0]=true，其它全为false。
动态规划的返回值
dp.back()[m]成立的最大m。
代码
核心代码
classSolution{public:intmaxTotalReward(vector<int>& rewardValues){constint N = rewardValues.size();sort(rewardValues.begin(), rewardValues.end());constint M = rewardValues.back(); vector<vector<bool>>dp(N+1,vector<bool>(M*2+1)); dp[0][0]=true;for(int i =0; i < N; i++){ dp[i +1]= dp[i];for(int m =0; m < rewardValues[i]; m++){ dp[i +1][m + rewardValues[i]]= dp[i +1][m + rewardValues[i]]|| dp[i][m];}}for(int m =2* M; m >M; m--){if(dp.back()[m]){return m;}}return M;}};单元测试
vector<int> rewardValues;TEST_METHOD(TestMethod1){ rewardValues ={1,3};auto res =Solution().maxTotalReward(rewardValues);AssertEx(4, res);}TEST_METHOD(TestMethod11){ rewardValues ={1,1,3,3};auto res =Solution().maxTotalReward(rewardValues);AssertEx(4, res);}TEST_METHOD(TestMethod12){ rewardValues ={1,6,4,3,2};auto res =Solution().maxTotalReward(rewardValues);AssertEx(11, res);}扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
