赛罕区城乡建设局网站,如何做流量网站,做网站被骗该咋样做,常州网络推广哪家好目录
1402. 做菜顺序
题目描述#xff1a;
实现代码与解析#xff1a;
暴力
原理思路#xff1a;
动态规划
原理思路#xff1a;
贪心
原理思路#xff1a; 1402. 做菜顺序
题目描述#xff1a; 一个厨师收集了他 n 道菜的满意程度 satisfaction #xff0c;这…目录
1402. 做菜顺序
题目描述
实现代码与解析
暴力
原理思路
动态规划
原理思路
贪心
原理思路 1402. 做菜顺序
题目描述 一个厨师收集了他 n 道菜的满意程度 satisfaction 这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间包含之前每道菜所花费的时间乘以这道菜的满意程度也就是 time[i]*satisfaction[i] 。
返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。
你可以按 任意 顺序安排做菜的顺序你也可以选择放弃做某些菜来获得更大的总和。
示例 1
输入satisfaction [-1,-8,0,5,-9]
输出14
解释去掉第二道和最后一道菜最大的 like-time 系数和为 (-1*1 0*2 5*3 14) 。每道菜都需要花费 1 单位时间完成。
示例 2
输入satisfaction [4,3,2]
输出20
解释可以按照任意顺序做菜 (2*1 3*2 4*3 20)示例 3
输入satisfaction [-1,-4,-5]
输出0
解释大家都不喜欢这些菜所以不做任何菜就可以获得最大的 like-time 系数。提示
n satisfaction.length1 n 500-1000 satisfaction[i] 1000
实现代码与解析
暴力
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {int n satisfaction.size();sort(satisfaction.begin(), satisfaction.end());int res 0;for (int i 0; i n; i) {int cur 0;int cnt 1;for (int j i; j n; j) {cur cnt * satisfaction[j];cnt;}res max(res, cur);}return res;}
};
原理思路 数据少可以直接暴力。主要介绍动态规划的写法。
动态规划
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {int n satisfaction.size();sort(satisfaction.begin(), satisfaction.end());vectorvectorint f(n 1, vectorint(n 1, 0));int res 0;for (int i 1; i n; i) {for (int j 1; j i; j) {f[i][j] f[i - 1][j - 1] satisfaction[i - 1] * j; // i jif (i j) {f[i][j] max(f[i][j], f[i - 1][j]);}}}for (int i 1; i n; i) {res max(f[n][i], res);}return res;}
};
原理思路 转换为背包问题由于前 i 个数在数组中是包含下标0和之前的数所以算的时候f[i]其实算的是遍历到satisfaction[i - 1]的值感觉这种写法很容易让人在思考时绕晕。 正常来说在自己控制输入时(acm模式把数据在下标1的位置开始输入这样不仅可以避免考虑边界问题还能简化代码。
dp数组含义 f[i][j] 为 在前 i 个数 中选择 j 个数可以获取的最大值。
递推式 f[i][j] f[i - 1][j - 1] satisfaction[i - 1] * j; 当 i j 时前 i 个 选择 j 个说明当前这个必须选那么前 i - 1个就选择了j - 1个。 f[i][j] max(f[i][j], f[i - 1][j]); 当 i j 时前 i 个 选择 j 个前 i - 1 个 选择 j 个选择第j个数的最大值与不选择第j个的最大值比较取max。 为什么先排序 如果把一个大的数放在前面那么它能选择的满意度只能是小的而把其放在后面则可以用动态规划从满意度0一直选到大的满意度这样才能考虑到最优的选择情况。体现在代码中就是
satisfaction[i - 1] * j 其实原理和01背包思想是一致的多了个排序。只不过容量为n每个数的质量相当于1而已。
之前写的背包详解。可以看看。
动态规划0-1背包、完全背包问题 | 详细原理解释 | 代码及优化C_c完全背包问题 动态规划-CSDN博客
贪心
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {sort(satisfaction.begin(), satisfaction.end(), greaterint());int cur 0, res 0;for (int t: satisfaction) {if (cur t 0) break;cur t;res cur;}return res;}
};
原理思路 贪心思路就是不断选最大的如果不加权的总和小于0了肯定会变小就不再选。严格的证明可以看力扣的证明。 其实自己带入一些样例就懂了就是逆向选择每次符合条件时res加上cur像是大于零的后缀和相加。
