【C++动态规划 贪心】3180. 执行操作可获得的最大总奖励 I|1848

本文涉及知识点

C++贪心
C++动态规划

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++**实现。