做网站一定要虚拟主机吗,如何创办自己的网站,企业注册信息查询单怎么打印,番禺网站建设公司贪心算法 什么是贪心算法 一个贪心算法总是做出当前最好的选择#xff0c;也就是说#xff0c;它期望通过局部最优选择从而得到全局最优的解决方案。 ----《算法导论》 贪心算法(Greedy Method): 所谓贪心算法就是重复地(或贪婪地)根据一个法则挑选解的一部分。当挑选完毕…贪心算法 什么是贪心算法 一个贪心算法总是做出当前最好的选择也就是说它期望通过局部最优选择从而得到全局最优的解决方案。 ----《算法导论》 贪心算法(Greedy Method): 所谓贪心算法就是重复地(或贪婪地)根据一个法则挑选解的一部分。当挑选完毕时最优解也就出现了。 贪心算法的几个核心问题
没有后悔药。一旦做出选择不可以后悔。有可能得到的不是最优解 而是最优解的近似解。选择什么样的贪心策略直接决定算法的好坏。
解决贪心算法的策略 贪心策略 确定一个贪心策略即选择一个好的方案。 局部最优解 一步一步地的到局部最优解。 全局最优解 将所有的局部最优解合成为原来问题的一个最优解。 tips 想想我们的冒泡排序
贪心算法与动态规划算法的区别 贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择不能回退。动态规划则会保存以前的运算结果并根据以前的结果对当前进行选择有回退功能。 再谈股票问题II
问题 [力扣122]122. 买卖股票的最佳时机 II - 力扣LeetCode 问题描述
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。
最大总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
最大总利润为 4 。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0。解决方案 使用贪心算法解决。 从“贪心”(获取最大利润)角度考虑如果当天卖出的价格高于前一天买入的价格就卖出保证利润的最大化。 if(prices[i] prices[i-1]){profits prices[i] - prices[i-1];
}参考实现
class Solution {public int maxProfit(int[] prices) {int profit 0;for (int i 1; i prices.length; i) {if(prices[i]prices[i-1]){profit prices[i] - prices[i-1];}}return profit;}
}找零钱问题
问题描述
商店售货员找给 1 个顾客 n 元用以下七种面值的纸币100 元50 元20 元10 元5 元2 元1 元。
思考如果商店售货员找给 1 个顾客 63元假设钱币的面值有九种100 元50 元20 元10 元5 元2 元1 元。用贪婪算法得到的是该问题的最优解吗 动态规划(DP) package com.ffyc.greedy;import java.util.Arrays;public class MoneyGreedyDp {public int coinChange(int[] nums, int amount) {int n nums.length;int[] dp new int[amount1];for(int m 1; m amount; m){dp[m] amount1;for(int j 0; jn;j){if(nums[j] m ){dp[m] Math.min(dp[m],dp[m-nums[j]]1);}}}if(dp[amount] amount){return -1;} else{return dp[amount];}}public static void main(String[] args) {int[] nums {1, 50, 2, 5, 100, 10, 20};int mount 63;new MoneyGreedy().greedy(nums, mount);}
}贪心算法 先从货币值大的开始扫描比如先选50,则剩余13元再选择10元则剩余3元。采用此策略直到扫描终止。 package com.ffyc.greedy;import java.util.Arrays;public class MoneyGreedy {public void greedy(int[] nums, int amount) {int n nums.length;//对零钱排序Arrays.sort(nums);int[] result new int[n];for (int i n-1; i 0; i--) {if (amount nums[i]) {result[i] amount / nums[i];amount amount % nums[i];}}if(amount 0) {System.out.println(剩余amount找零失败....);return;}System.out.println(Arrays.toString(result));}public static void main(String[] args) {int[] nums {1, 50, 2, 5, 100, 10, 20};int mount 63;new MoneyGreedy().greedy(nums, mount);}
}
