江苏有什么网站找工程建设人员,wordpress qq空间主题,互联网专线做网站怎么做数据,免费网站空间可上传网站一、贪心例子
贪心算法或贪婪算法的核心思想是#xff1a;
1. 将寻找最优解的问题分为若干个步骤
2. 每一步骤都采用贪心原则#xff0c;选取当前最优解
3. 因为没有考虑所有可能#xff0c;局部最优的堆叠不一定让最终解最优 贪心算法是一种在每一步选择中都采取在当前…一、贪心例子
贪心算法或贪婪算法的核心思想是
1. 将寻找最优解的问题分为若干个步骤
2. 每一步骤都采用贪心原则选取当前最优解
3. 因为没有考虑所有可能局部最优的堆叠不一定让最终解最优 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题如最小生成树、背包问题等。
贪心算法的应用
1. 背包问题给定一组物品和一个背包每个物品有一定的重量和价值要求在不超过背包容量的情况下尽可能多地装入物品。
2. 活动选择问题在一个活动集合中每次只能参加一个活动问如何安排时间以最大化所有活动的收益。
3. 编辑距离问题给定两个字符串求它们之间的最小编辑距离即将一个字符串转换为另一个字符串所需的最少操作次数。
4. 网络流问题给定一张有向图和一些起点和终点求最大流量。
5. 找零问题给定一定数量的硬币和需要找零的金额求使用最少的硬币数。 常见问题及解答
1. 贪心算法一定会找到最优解吗
答不一定。贪心算法只保证在每一步选择中都是最优的但并不能保证整个问题的最优解。例如背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。
2. 如何判断一个问题是否适合用贪心算法解决
答一个问题如果可以用递归的方式分解为若干个子问题且每个子问题都有明确的最优解即局部最优那么这个问题就可以用贪心算法解决。
3. 贪心算法的时间复杂度是多少
答贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说对于规模较小的问题贪心算法的时间复杂度可以达到O(nlogn)或O(n^2)对于规模较大的问题可能需要(O^3)或更高。 几个贪心的例子
Dijkstra
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited true;
} 没找到最短路径的例子负边存在时可能得不到正确解问题出在贪心的原则会认为本次已经找到了该顶点的最短路径下次不会再处理它curr.visited true)与之对比Bellman-Ford并没有考虑局部距离最小的顶点而是每次都处理所有边所以不会出错当然效率不如Dijkstra
Prim
// ...
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vertex curr chooseMinDistVertex(list);// 更新当前顶点邻居距离updateNeighboursDist(curr);// 移除当前顶点list.remove(curr);// 标记当前顶点已经处理过curr.visited true;
}
Kruskal
// ...
while (list.size() size - 1) {// 选取当前【距离最短】的边Edge poll queue.poll();// 判断两个集合是否相交int i set.find(poll.start);int j set.find(poll.end);if (i ! j) { // 未相交list.add(poll);set.union(i, j); // 相交}
}
其它贪心的例子 选择排序、堆排序 拓扑排序入度最小 并查集合中的 union by size 和 union by height 哈夫曼编码 钱币找零英文搜索关键字 change-making problem find Minimum number of Coins 任务编排 求复杂问题的近似解 二、零钱兑换问题
1. 零钱兑换
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11输出3解释11 5 5 1
示例 2
输入coins [2], amount 3输出-1
示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 2^31 - 10 amount 10^4
解法一穷举法。超出时间限制 private int min -1;public int coinChange(int[] coins, int amount) {rec(0, coins, amount, new AtomicInteger(-1));return min;}// count代表某一组合钱币的总数private void rec(int index, int[] coins, int remainder, AtomicInteger count) {count.incrementAndGet();if (remainder 0) {if (min -1) {min count.get();} else {min Integer.min(min, count.get());}} else if (remainder 0) {for (int i index; i coins.length; i) {rec(i, coins, remainder - coins[i], count);}}count.decrementAndGet();}
解法二动态规划
class Solution {public int coinChange(int[] coins, int amount) {int[] dp new int[amount 1];Arrays.fill(dp, amount 1);// 0元所需的硬币数为0dp[0] 0;// 遍历每一个硬币for (int coin : coins) {// 从coin到amount更新dp数组for (int i coin; i amount; i) {// dp[i]为凑成金额i所需的最少硬币个数dp[i] Math.min(dp[i], dp[i - coin] 1);}}return dp[amount] amount 1 ? -1 : dp[amount];}
}
解法三贪心算法。只能通过部分测试用例
贪心算法得到的解不一定是全局最优解 // 贪心算法 可能得到错误的解public int coinChange(int[] coins, int amount) {Arrays.sort(coins);reverseArray(coins);int remainder amount;int count 0;for (int coin : coins) {// 从大面额的金币开始凑while (remainder coin) {remainder - coin;count;}if (remainder coin) {remainder 0;count;break;}}if (remainder 0) {return -1;} else {return count;}}private void reverseArray(int[] coins) {int left 0;int right coins.length - 1;while (left right) {// 交换元素int temp coins[left];coins[left] coins[right];coins[right] temp;left;right--;}} 2. 零钱兑换Ⅱ
给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1
输入amount 5, coins [1, 2, 5]
输出4
解释有四种方式可以凑成总金额
55
5221
52111
511111示例 2
输入amount 3, coins [2]
输出0
解释只用面额 2 的硬币不能凑成总金额 3 。示例 3
输入amount 10, coins [10]
输出1提示
1 coins.length 3001 coins[i] 5000coins 中的所有值 互不相同0 amount 5000
解法一每次都会重复计算相同的子问题导致时间复杂度较高。超出时间限制
class Solution {public int change(int amount, int[] coins) {return rec(0, coins, amount, new LinkedList(), true);}/*** 求凑成剩余金额的解的个数* param index 当前硬币索引* param coins 硬币面值数组* param remainder 剩余金额* param stack* param first* return*/private int rec(int index, int[] coins, int remainder, LinkedListInteger stack, boolean first) {if(!first) {stack.push(coins[index]);}int count 0;// 情况1剩余金额 0 - 无解if(remainder 0) {print(无解, stack);}// 情况2剩余金额 0 - 找到解else if(remainder 0) {print(有解, stack);count 1;}// 情况3剩余金额 0 - 继续递归else {for (int i index; i coins.length; i) {count rec(i, coins, remainder - coins[i], stack, false);}}// 回溯backtrackif(!stack.isEmpty()) {stack.pop();}return count;}private static void print(String prompt, LinkedListInteger stack) {ArrayListInteger print new ArrayList();ListIteratorInteger iterator stack.listIterator(stack.size());while(iterator.hasPrevious()) {print.add(iterator.previous());}System.out.println(prompt print);}
}
解法二动态规划。执行耗时2ms
使用一个一维数组dp来保存到达每个金额所需的不同硬币组合的数量
public int change(int amount, int[] coins) { int[] dp new int[amount 1]; dp[0] 1; // 只有一种方式凑成0元即不使用任何硬币 // 动态规划通过循环每一个硬币来计算不同金额的组合数 for (int coin : coins) { for (int i coin; i amount; i) { dp[i] dp[i - coin]; } } return dp[amount];
} 三、Huffman编码问题
1. 问题引入
1什么是编码
答简单来说就是建立【字符】到【数字】的对应关系如下面大家熟知的ASCⅡ编码表例如可以查表得知字符【a】对应的数字是十六进制数【0x61】
\000102030405060708090a0b0c0d0e0f0000000102030405060708090a0b0c0d0e0f0010101112131415161718191a1b1c1d1e1f002020!#$%()*,-./00300123456789:;?0040ABCDEFGHIJKLMNO0050PQRSTUVWXYZ[\]^_0060abcdefghijklmno0070pqrstuvwxyz{|}~7f
注一些直接以十六进制数字标识的是那些不可打印字符 2传输时的编码
java中每个char对应的数字会占用固定长度2个字节
如果在传输中仍采用上述规则传递abbccccccc这10个字符
实际的字节为 006100620062006300630063006300630063006316进制表示总共20个字节不经济
现在希望找到一种最节省字节的传输方式怎么办
假设传输的字符中只包含abc这3个字符有同学重新设计一张二进制编码表见下图
0表示a1表示b10表示c
现在还是传递abbccccccc这10个字符
实际的字节为 01110101010101010 二进制表示总共需要17bits也就是2字节多一点行不行
不行因为解码会出现问题因为10会被错误的解码成为ba而不是c
解码后的结果为 abbbababababababa是错误的。 怎么解决必须保证编码后的二进制数字要能区分它们的前缀prefix-free用满二叉树结构编码可以确保前缀不重复 向左走为0向右走为1走到叶子字符累计起来的0和1就是该字符的二进制编码a的编码为0b的编码为10c的编码为11
现在还是传递 abbccccccc 这 10 个字符
实际的字节为 0101011111111111111二进制表示总共需要 19 bits也是 2 个字节多一点并且解码没有问题了行不行
这次解码没有问题了但是并非最少字节因为c的出现频率高7次a的出现频率低1次因此出现频率高的字符编码成短数字更经济。
考察下面的树 00表示a01表示b1表示c
现在还是传递image-20230616095129461 实际的字节为 000101 1111111 二进制表示 总共需要 13 bits这棵树就称之为 Huffman 树 根据 Huffman 树对字符和数字进行编解码就是 Huffman 编解码 2. Huffman树及Huffman编解码
注为了简单期间编码解码都用字符串演示实际应该按bits编解码
package com.itheima.algorithms.greedy;import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;/*** Huffman树及编解码*/
public class HuffmanTree {/*** Huffman树的构建过程* 1. 将统计了出现频率的字符放入到优先级队列* 2. 每次出队两个频次最低的元素给他俩找个爹* 3. 把爹重新放入队列重复 2~3* 4. 当队列中只剩一个元素时Huffman树构建完成*/static class Node {Character ch; // 字符int freq; // 频次Node left; // 左孩子Node right; // 右孩子String code; // 编码public Node(Character ch) {this.ch ch;}public Node(int freq, Node left, Node right) {this.freq freq;this.left left;this.right right;}public int getFreq() {return freq;}public boolean isLeaf() {return left null;}Overridepublic String toString() {return Node{ ch ch , freq freq };}}String str;Node root;MapCharacter, Node map new HashMap();public HuffmanTree(String str) {this.str str;// 1. 统计频率char[] chars str.toCharArray();for (char ch : chars) {/*if(!map.containsKey(ch)) {map.put(ch, new Node(ch));}Node node map.get(ch);node.freq;*/Node node map.computeIfAbsent(ch, Node::new);node.freq;}// 2. 构造树PriorityQueueNode queue new PriorityQueue(Comparator.comparingInt(Node::getFreq));queue.addAll(map.values());while (queue.size() 2) {// 每次出队两个频次最低的元素给他俩找个爹Node x queue.poll();Node y queue.poll();int freq x.freq y.freq;// 把爹重新放入队列queue.offer(new Node(freq, x, y));}root queue.poll();// 3. 计算每个字符的编码int bit dfs(root, new StringBuilder());for (Node node : map.values()) {System.out.println(node , code node.code);}System.out.println(字符串 str 编码总共占用了 bit bit);}private int dfs(Node node, StringBuilder code) {int sum 0;if (node.isLeaf()) {// 叶子节点node.code code.toString();// 4. 统计字符串编码后占用多少bitsum node.freq * node.code.length();} else {sum dfs(node.left, code.append(0));sum dfs(node.right, code.append(1));}// 回溯if (code.length() 0) {code.deleteCharAt(code.length() - 1);}return sum;}// 编码public String encode() {char[] chars str.toCharArray();StringBuilder sb new StringBuilder();for (char ch : chars) {sb.append(map.get(ch).code);}return sb.toString();}/*** 解码* 从根节点开始寻找数字对应的字符* 数字是0向左走* 数字是1向右走* 如果没走到头每走一步数字的索引 i* 走到头就可以找到解码字符再将node重置为根节点* param str - code* return*/public String decode(String str) {char[] chars str.toCharArray();int i 0;StringBuilder sb new StringBuilder();Node node root;while(i chars.length) {if(!node.isLeaf()) { // 非叶子if(chars[i] 0) {// 向左走node node.left;} else if(chars[i] 1){// 向右走node node.right;}i;}if(node.isLeaf()) {sb.append(node.ch);node root;}}return sb.toString();}public static void main(String[] args) {HuffmanTree tree new HuffmanTree(abbccccccc);String encode tree.encode();System.out.println(encode);System.out.println(tree.decode(encode));}
}3. 连接木棍的最低费用
为了装修新房你需要加工一些长度为正整数的棒材 sticks。
如果要将长度分别为 X 和 Y 的两根棒材连接在一起你需要支付 X Y 的费用。 由于施工需要你必须将所有棒材连接成一根。
返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。
示例 1: 输入sticks [2,4,3] 输出14 解释先将 2 和 3 连接成 5花费 5再将 5 和 4 连接成 9总花费为 14。
示例 2 输入sticks [1,8,3,5] 输出30
提示 1 sticks.length 10^4 1 sticks[i] 10^4
解法一哈夫曼树建树
class Solution {public int connectSticks(int[] sticks) {// 1. 将元素放入优先队列PriorityQueueInteger queue new PriorityQueue();for (int stick : sticks) {queue.offer(stick);}int sum 0;while(queue.size() 2) {// 每次取最小的两个Integer x queue.poll();Integer y queue.poll();int c x y;sum c;// 将父节点入队queue.offer(c);}return sum;}
} 四、活动选择问题
1. 举办最多的活动
要在应该会议室举办n个活动 - 每个活动有它们各自的起始和结束时间 - 找出时间上互不冲突的活动组合能够充分利用会议室举办的活动次数最多
package com.itheima.algorithms.greedy;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;/*** 活动区间选择 - 贪心算法* 无重叠区间本质就是活动选择问题*/
public class ActivitySelectionProblem {/*** 要在应该会议室举办n个活动* - 每个活动有它们各自的起始和结束时间* - 找出时间上互不冲突的活动组合能够充分利用会议室举办的活动次数最多** 例1* 0 1 2 3 4 5 6 7 8 9* |-------)* |-------)* |-------)* 例2* 0 1 2 3 4 5 6 7 8 9* |---)* |---)* |-----------------------)* |-------)* |---)* |---------------)** 几种贪心策略* 1. 优先选择持续时间最短的活动 ×* 0 1 2 3 4 5 6 7 8 9* 1 |---------------) 选中* 2 |-------)* 3 |---------------) 选中** 2. 优先选择冲突最少的活动 ×* 编号 0 1 2 3 4 5 6 7 8 9 冲突次数 实际解* 1 |-------) 3 选中* 2 |-------) 4* 3 |-------) 4* 4 |-------) 4* 5 |-------) 4 选中* 6 |-------) 2* 7 |-----------) 4 选中* 8 |-------) 4* 9 |-------) 4* 10 |-------) 4* 11 |-------) 3 选中** 3. 优先选择最先开始的活动 ×* 0 1 2 3 4 5 6 7 8 9* 2 |---) 选中* 3 |---) 选中* 4 |---) 选中* 1 |-----------------------------------)** 4. 优先选择最先结束的活动 √*/// 活动类static class Activity {int index;int start;int finish;public Activity(int index, int start, int finish) {this.index index;this.start start;this.finish finish;}public int getFinish() {return finish;}Overridepublic String toString() {return Activity( index );}}public static void main(String[] args) {Activity[] activities new Activity[] {new Activity(1, 2, 4),new Activity(0, 1, 3),new Activity(2, 3, 5)};Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));System.out.println(Arrays.toString(activities));select(activities, activities.length);}private static void select(Activity[] activities, int n) {ListActivity result new ArrayList();Activity prev activities[0]; // 上次被选中的活动result.add(prev);for (int i 1; i n; i) {Activity curr activities[i]; // 正在处理的活动if(curr.start prev.finish) {result.add(curr);prev curr;}}for (Activity activity : result) {System.out.println(activity);}}
}2. 无重叠区间
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:
输入: intervals [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。示例 3:
输入: intervals [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示:
1 intervals.length 10^5intervals[i].length 2-5 * 10^4 starti endi 5 * 10^4
解法一贪心算法
class Solution {/*** 找到不重叠的最多的活动数count即活动选择问题原始需求* 在此基础之上活动总数 - count就是题目要的排除数量* * param intervals* return*/public int eraseOverlapIntervals(int[][] intervals) {// 1. 将集合元素按照结束时间升序排序Arrays.sort(intervals, Comparator.comparingInt(a - a[1]));int count 1; // 默认选择第一个int i 0; // 前一个for (int j 0; j intervals.length; j) {// 后一个的开始时间 前一个的结束时间if (intervals[j][0] intervals[i][1]) {i j;count;}}return intervals.length - count;}
}
解法二动态规划
class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length 0)return 0;// 按结束时间排序Arrays.sort(intervals, (a, b) - Integer.compare(a[1], b[1]));// 创建一个数组保存结束时间int n intervals.length;int[] ends new int[n];ends[0] intervals[0][1];int count 1; // 至少包括第一个区间for (int i 1; i n; i) {// 检查重叠if (intervals[i][0] ends[count - 1]) {ends[count] intervals[i][1]; // 添加到不重叠区间}}return n - count; // 总数减去不重叠的数量}
} 五、分数背包问题
package com.itheima.algorithms.greedy;import java.util.Arrays;
import java.util.Comparator;public class FractionalKnapsackProblem {/*1. n个物品都是液体有重量和价值2. 现在你要取走 10升 的液体3. 每次可以不拿全拿或拿一部分问最高价值是多少编号 重量(升) 价值0 4 24 水1 8 160 牛奶 选中 7/82 2 4000 五粮液 选中3 6 108 可乐4 1 4000 茅台 选中8140简化起见给出的数据都是【价值/重量】能够整除避免计算结果中出现小数增加心算难度*/static class Item {int index;int weight;int value;public Item(int index, int weight, int value) {this.index index;this.weight weight;this.value value;}// 单位价值public int unitValue() {return value / weight;}Overridepublic String toString() {return Item{ index };}}public static void main(String[] args) {Item[] items new Item[] {new Item(0, 4, 24),new Item(1, 8, 160),new Item(2, 2, 4000),new Item(3, 6, 108),new Item(4, 1, 4000)};System.out.println(select(items, 10));}private static int select(Item[] items, int total) {// 1. 按单位价值降序排序Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());int max 0;for (Item item : items) {if(total item.weight) {// 可以拿完total - item.weight;max item.value;} else {// 拿不完max item.unitValue() * total;break;}}return max;}
}六、0-1背包问题
对于此问题贪心算法可能无法得到最优解
package com.itheima.algorithms.greedy;import java.util.Arrays;
import java.util.Comparator;public class KnapsackProblem {/*1. n个物品都是固体有重量和价值2. 现在你要取走不超过 10克 的物品3. 每次可以 不拿 或 全拿问最高价值是多少编号 重量(g) 价值(元)0 1 1_000_000 钻戒一枚1 4 1600 黄金一块2 8 2400 红宝石戒指一枚3 5 30 白银一块*/static class Item {int index;int weight;int value;public Item(int index, int weight, int value) {this.index index;this.weight weight;this.value value;}public int unitValue() {return value / weight;}Overridepublic String toString() {return Item( index );}}public static void main(String[] args) {Item[] items new Item[]{new Item(0, 1, 1000000),new Item(1, 4, 1600),new Item(2, 8, 2400),new Item(3, 5, 30)};select(items, 10);}private static void select(Item[] items, int total) {Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());int max 0; // 最大价值for (Item item : items) {System.out.println(item);if (total item.weight) { // 可以拿完total - item.weight;max item.value;}}System.out.println(最大价值是: max);}
} 贪心算法的局限
问题名称是否能用贪心得到最优解替换解法Dijkstra(不存在负边)✔️Dijkstra(存在负边)❌Bellman-FordPrim✔️Kruskal✔️零钱兑换❌动态规划Huffman 树✔️活动选择问题✔️分数背包问题✔️0-1 背包问题❌动态规划
