贪心、分治
贪心(Greedy)问题1:最优装载(加勒比海盗)问题2:零钱兑换零钱兑换的另一个例子贪心注意点问题3:0-1背包0-1 背包 - 实例一些习题分治(Divide And Conquer)主定理(Master Theorem)问题1:最大连续子序列和解法1 – 暴力出奇迹暴力出奇迹 – 优化解法2 – 分治问题2:大数乘法数据结构与算法笔记:恋上数据结构笔记目录
贪心(Greedy)
贪心策略,也称为贪婪策略
每一步都采取当前状态下最优的选择(局部最优解),从而希望推导出全局最优解
贪心的应用
哈夫曼树最小生成树算法:Prim、Kruskal最短路径算法:Dijkstra
问题1:最优装载(加勒比海盗)
贪心策略:每一次都优先选择重量最小的古董
① 选择重量为 2 的古董,剩重量 28
② 选择重量为 3 的古董,剩重量 25
③ 选择重量为 4 的古董,剩重量 21
④ 选择重量为 5 的古董,剩重量 16
⑤ 选择重量为 7 的古董,剩重量 9根据上面的选择,最多能装载 5 个古董
import java.util.Arrays;/*** 有一天,海盗们截获了一艘装满各种各样古董的货船,每一件古董都价值连城,一旦打碎就失去了它的价值* 海盗船的载重量为 W,每件古董的重量为 𝑤i,海盗们该如何把尽可能多数量的古董装上海盗船?* 比如 W 为 30,Wi 分别为 3、5、4、10、7、14、2、11*/public class Pirate {public static void main(String[] args) {int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};Arrays.sort(weights); // 排序, 默认从小到大int capacity = 30; // 最大容量int weight = 0, count = 0;// 每次优先选择重量最小的古董for (int i = 0; i < weights.length && weight < capacity; i++) {int newWeight = weights[i] + weight;if (newWeight <= capacity) {weight = newWeight;count++;// System.out.println(weights[i]);}}// System.out.println("装了 " + count + " 件古董。");}}
23457装了 5 件古董。
问题2:零钱兑换
假设有 25 分、10 分、5 分、1 分的硬币,现要找给客户 41 分的零钱,如何办到硬币个数最少?
贪心策略:每一次都优先选择面值最大的硬币
① 选择 25 分的硬币,剩 16 分
② 选择 10 分的硬币,剩 6 分
③ 选择 5 分的硬币,剩 1 分
④ 选择 1 分的硬币最终的解是共 4 枚硬币
25 分、10 分、5 分、1 分硬币各一枚
import java.util.Arrays;/*** 假设有 25 分、10 分、5 分、1 分的硬币,* 现要找给客户 41 分的零钱,如何办到硬币个数最少?*/public class CoinChange {public static void main(String[] args) {// 三种写法, 结果是一样的coinChange1(new Integer[] {25, 10, 5, 1}, 41);coinChange2(new Integer[] {25, 10, 5, 1}, 41);coinChange3(new Integer[] {25, 10, 5, 1}, 41);}// 写法1static void coinChange1(Integer[] faces, int money) {Arrays.sort(faces); // 排序, 默认从小到大int coins = 0;// 贪心策略, 选择面值最大的硬币, 由于顺序小->大, 从后往前放for (int i = faces.length - 1; i >= 0; i--) {// 如果面值比我要的钱大, 进行下一轮if (money < faces[i]) continue;// System.out.println(faces[i]);money -= faces[i];coins++;i = faces.length;}// System.out.println("使用了" + coins + "个硬币。");}// 写法2static void coinChange2(Integer[] faces, int money) {// 排序, 传入了比较器, 所以是从大到小排序Arrays.sort(faces, (Integer f1, Integer f2) -> f2 - f1);// 贪心策略, 选择面值最大的硬币, 由于顺序大->小, 从前往后放int coins = 0, i = 0;while (i < faces.length) {if (money < faces[i]) {i++;continue;}// System.out.println(faces[i]);money -= faces[i];coins++;// i = 0; // 这步是不需要的}// System.out.println("使用了" + coins + "个硬币。");}// 写法3static void coinChange3(Integer[] faces, int money) {Arrays.sort(faces);// 贪心策略, 选择面值最大的硬币, 由于顺序小->大, 从后往前放int coins = 0, idx = faces.length - 1;while (idx >= 0) {while (money >= faces[idx]){// System.out.println(faces[idx]);money -= faces[idx];coins++;}idx--;}// System.out.println("使用了" + coins + "个硬币。");}}
251051使用了4个硬币。
零钱兑换的另一个例子
将之前的代码的输入修改一下,可以得出结果:发现确实没有得到最优解。
public static void main(String[] args) {coinChange1(new Integer[] {25, 10, 5, 1}, 41);coinChange2(new Integer[] {25, 10, 5, 1}, 41);coinChange3(new Integer[] {25, 20, 5, 1}, 41);}
255551使用了5个硬币。
贪心注意点
贪心策略并不一定能得到全局最优解
因为一般没有测试所有可能的解,容易过早做决定,所以没法达到最佳解贪图眼前局部的利益最大化,看不到长远未来,走一步看一步
优点:简单、高效、不需要穷举所有可能,通常作为其他算法的辅助算法来使用
缺点:鼠目寸光,不从整体上考虑其他可能,每次采取局部最优解,不会再回溯,因此很少情况会得到最优解
问题3:0-1背包
0-1 背包 - 实例
Article类 模拟物品:
package com.mj.ks;public class Article {int weight; // 重量int value; // 价值double valueDensity; // 价值密度public Article(int weight, int value) {this.weight = weight;this.value = value;valueDensity = value * 1.0 / weight;}@Overridepublic String toString() {return "Article [weight=" + weight + ", value=" + value + ", ValueDensity=" + valueDensity + "]";}}
0-1 背包问题:分别按照价值主导、重量主导、价值密度主导解决。
package com.mj.ks;import java.util.Arrays;import parator;import java.util.LinkedList;import java.util.List;/*** 0-1 背包问题* @author yusael*/public class Knapsack {public static void main(String[] args) {select("价值主导", (Article a1, Article a2) -> {// 价值大的优先return a2.value - a1.value;});select("重量主导", (Article a1, Article a2) -> {// 重量小的优先return a1.weight - a2.weight; });select("价值密度主导", (Article a1, Article a2) -> {// 价值密度大的优先return pare(a2.valueDensity, a1.valueDensity);});}/*** 以一个属性为主导实现贪心策略* @param title 显示标题* @param cmp 比较器决定主导属性, [价值、重量、价值密度]*/static void select(String title, Comparator<Article> cmp) {// 模拟题意的物品Article[] articles = new Article[] {new Article(35, 10), new Article(30, 40),new Article(60, 30), new Article(50, 50),new Article(40, 35), new Article(10, 40),new Article(25, 30)};// 通过比较器, 按某个主导属性进行排序Arrays.sort(articles, cmp);// 以某个属性为主导, 实现贪心策略int capacity = 150, weight = 0, value = 0;List<Article> selectedArticles = new LinkedList<Article>(); // 选择的物品集合for (int i = 0; i < articles.length && weight < capacity; i++) {int newWeight = weight + articles[i].weight;if (newWeight <= capacity) {weight = newWeight;value += articles[i].value;selectedArticles.add(articles[i]);}}System.out.println("-----------------------------");System.out.println("【" + title + "】");System.out.println("总价值: " + value);for (Article article : selectedArticles) {System.out.println(article);}}}
-----------------------------【价值主导】总价值: 165Article [weight=50, value=50, ValueDensity=1.0]Article [weight=30, value=40, ValueDensity=1.3333333333333333]Article [weight=10, value=40, ValueDensity=4.0]Article [weight=40, value=35, ValueDensity=0.875]-----------------------------【重量主导】总价值: 155Article [weight=10, value=40, ValueDensity=4.0]Article [weight=25, value=30, ValueDensity=1.2]Article [weight=30, value=40, ValueDensity=1.3333333333333333]Article [weight=35, value=10, ValueDensity=0.2857142857142857]Article [weight=40, value=35, ValueDensity=0.875]-----------------------------【价值密度主导】总价值: 170Article [weight=10, value=40, ValueDensity=4.0]Article [weight=30, value=40, ValueDensity=1.3333333333333333]Article [weight=25, value=30, ValueDensity=1.2]Article [weight=50, value=50, ValueDensity=1.0]Article [weight=35, value=10, ValueDensity=0.2857142857142857]
一些习题
分发饼干
用最少数量的箭引爆气球
买卖股票的最佳时机 II
种花问题
分发糖果
分治(Divide And Conquer)
分治,也就是分而治之。它的一般步骤是:
① 将原问题分解成若干个规模较小的子问题(子问题和原问题的结构一样,只是规模不一样)
② 子问题又不断分解成规模更小的子问题,直到不能再分解(直到可以轻易计算出子问题的解)
③ 利用子问题的解推导出原问题的解
因此,分治策略非常适合用递归。
需要注意的是:子问题之间是相互独立的。
分治的应用:
快速排序归并排序Karatsuba 算法(大数乘法)
主定理(Master Theorem)
问题1:最大连续子序列和
题目:leetcode_53_最大子序和
给定一个长度为 n 的整数序列,求它的最大连续子序列和
比如 –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6
这道题也属于最大切片问题(最大区段,Greatest Slice)
概念区分
子串、子数组、子区间:必须是连续的子序列:可以不连续
解法1 – 暴力出奇迹
穷举出所有可能的连续子序列,分别计算出它们的和,最后取它们中的最大值。
时间复杂度:O(n3),空间复杂度:O(1)
/*** 暴力*/static int maxSubArray(int [] nums) {if (nums == null || nums.length == 0) return 0;// 这里注意, 容易写成 int max = 0, 可能会出错, max 默认值必须是最小的值int max = Integer.MIN_VALUE; // 穷举, 列出所有可能的连续子序列, 分别计算它们的和, 最后取出最大值for (int begin = 0; begin < nums.length; begin++) {for (int end = begin; end < nums.length; end++) {int sum = 0; // sum是[begin, end]的和// nums[begin] 到 nums[end] 求和for (int i = begin; i <= end; i++) {sum += nums[i];}max = Math.max(max, sum); // 取最大值}}return max;}
这个结果应该不意外吧…
暴力出奇迹 – 优化
重复利用前面计算过的结果
时间复杂度:O(n2),空间复杂度:O(1)
/*** 暴力 - 优化*/static int maxSubArray(int [] nums) {if (nums == null || nums.length == 0) return 0;// 这里注意, 容易写成 int max = 0, 可能会出错, max 默认值必须是最小的值int max = Integer.MIN_VALUE;// 穷举, 列出所有可能的连续子序列, 分别计算它们的和, 最后取出最大值for (int begin = 0; begin < nums.length; begin++) {// 重复利用sum, 只有当begin修改才会重置int sum = 0;// begin不动, end修改的话, 子序列的和是叠加的, 无需每次都重新计算for (int end = begin; end < nums.length; end++) {sum += nums[end]; // sum是[begin, end]的和max = Math.max(max, sum); // 取最大值}}return max;}
至少不超时了。。。
解法2 – 分治
空间复杂度:O(logn)
时间复杂度:O(nlogn),跟归并排序、快速排序一样,利用主定理计算:T(n) = 2T(n/2) + O(n)
/*** 分治*/static int maxSubArray(int [] nums) {if (nums == null || nums.length == 0) return 0;return maxSubArray(nums, 0, nums.length);}static int maxSubArray(int[] nums, int begin, int end) {// 递归基: end - begin < 2, 说明只有一个元素, nums[begin] == nums[end]if (end - begin < 2) return nums[begin];int mid = (begin + end) >> 1;// 最长子序列是 [i, mid) + [mid, j) 的情况int leftMax = Integer.MIN_VALUE;int leftSum = 0;for (int i = mid - 1; i >= begin; i--) {// [i,mid)leftSum += nums[i];leftMax = Math.max(leftSum, leftMax);}int rightMax = Integer.MIN_VALUE;int rightSum = 0;for (int i = mid; i < end; i++) {// [mid, end)rightSum += nums[i];rightMax = Math.max(rightSum, rightMax);}// 最长子序列在 left部分, right部分的情况return Math.max(leftMax + rightMax,Math.max(maxSubArray(nums, begin, mid), // 最长子串在[begin, mid)的情况 maxSubArray(nums, mid, end) // 最长子串在[mid, end)的情况));}
可以看到这种解法特别快。。。
挖个坑,这题其实可以用动态规划解决。
问题2:大数乘法
【恋上数据结构】贪心(最优装载 零钱兑换 0-1背包) 分治(最大连续子序列和 大数乘法)
如果觉得《【恋上数据结构】贪心(最优装载 零钱兑换 0-1背包) 分治(最大连续子序列和 大》对你有帮助,请点赞、收藏,并留下你的观点哦!