失眠网 > 【恋上数据结构】贪心（最优装载零钱兑换 0-1背包）分治（最大连续子序列和大

【恋上数据结构】贪心（最优装载零钱兑换 0-1背包）分治（最大连续子序列和大

时间：2021-03-10 11:58:07

贪心、分治

贪心（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)的情况));}

可以看到这种解法特别快。。。

挖个坑，这题其实可以用动态规划解决。