贪心算法
1)Greedy algorithm
称之为贪心算法或者贪婪算法,核心思想是
- 将寻找最优解的问题分为若干个步骤
- 每一步骤都采用贪心原则,选取当前最优解
- 因为未考虑所有可能,局部最优的堆叠不一定得到最终解最优
贪心算法例子
Dijkstra
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vretex curr = chooseMinDistVertex(list);// 更新当前顶点到相邻顶点距离updateNeighboursDish(curr);// list集合中移除当前顶点list.remove(curr);// 标记当前顶点已被访问curr.visited = true;
}
- 未能找到最短路径:存在负边 情况,得不到正确解;
- 贪心原则会认为本次已找到该顶点的最短路径,使得该顶点赋为已访问 ;
- 与之对比,Bellman-Ford算法并未考虑局部距离最小顶点,而是每次处理所有边 ,不会出错,当然效率不如Dijkstra算法;
prim
while (!list.isEmpty()) {// 选取当前【距离最小】的顶点Vretex curr = chooseMinDistVertex(list);// 更新当前顶点到相邻顶点距离updateNeighboursDish(curr);// list集合中移除当前顶点list.remove(curr);// 标记当前顶点已被访问curr.visited = true;
}
prim与Dijkstra的区别在于,根据距离选取最小顶点不同,Dijkstra算法是一个累加距离,而prim算法中距离是跟相邻顶点间的距离 。
KrusKal
List<String> list = new ArrayList<>();
DisjoinSet set = new DisjoinSet(size);
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
- 哈夫曼编码
- 钱币找零
- 任务编排
- 近似算法
零钱兑换ⅡLeetcode518
递归实现
public class Leetcode518 {public int change(int[] coins, int amount) {return coinChange(coins, 0, amount, new LinkedList<>(), true);}public int coinChange(int[] coins, int index, int amount, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[i]);}int sum = 0;if (amount == 0) {System.out.printlin(stack);sum = 1;} else if (amount < 0) {System.out.println(stack)sum = 0;} else {for(int i = index; i < coins.length; i++) {sum += coinChange(coins, i, amount - coins[i], stack, false);}}if (!stack.isEmpty()) {stack.pop();}return sum;}
}
零钱兑换Leetcode322
递归实现
public class Leetcode322 {static int min = -1;public int change(int[] coins, int amount) {coinChange(coins, 0, amount, new AtomicInteger(-1), new LinkedList<Integer>(), true);return min;}public void coinChange(int[] coins, int index, int amount, AtomicInteger count, LinkedList<Integer> stack, boolean first) {if (!first) {stack.push(coins[i]);}count.incrementAndGet(); // count++;int sum = 0;if (amount == 0) {System.out.println(stack);if (min == -1) {min = min.get();} else {min = Math.min(min, count.get());}} else {for(int i = index; i < coins.length; i++) {sum += coinChange(coins, i, amount - coins[i], count, stack, false);}}count.decrementAndGet(); // count--; if (!stack.isEmpty()) {stack.pop();}return sum;}public static void main(String[] args) {int[] coins = {5, 2, 1};Leetcode322 leetcode = new Leetcode322();System.out.printlin(leetcode.coinChange(coins, 5));}
}
贪心实现
public class Leetcode322{public int coinChange(int[] coins, int amount) {// 前提是coins是降序排序int reminder = amount;int count;for(int coin : coins) {while (reminder > coin) {reminder -= coin;count++;}if (reminder == coin) {reminder -= coin;count++;break;}}if (reminder > 0) {return -1;} else {return count;}}}
但是这个代码放到Leetcode上跑,有些测试用例是不能通过。
动态规划实现
使用动态规划求解,如下面代码
public class Leetcode322{public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for(int coin : coins) {for(int j = coin; j < amount + 1; j++) {dp[j] = Math.min(dp[j], dp[j - coin] + 1);}}int r = dp[amount];return r > amount ? -1 : r;}}
哈夫曼编码
Huffman树构建过程
- 统计出现频次字符,放入优先级队列
- 每次出对两个频次最低元素(小顶堆),
- 当队列中只有一个元素时,构建Huffman树完成
public class 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;}int getFreq() {return freq;}boolean isLeaf() {return node.left == null;}@Overridepublic void toString() {return "Node{" +"ch=" + ch + ", freq=" + freq +"}";}}String str;Node root;HashMap<Character, Node> map = new HashMap<>();public Huffman(String str) {this.str = str;char[] chars = str.toCharArray();// 1.统计频次for(char ch : chars) {if (!map.containsKey(ch)) {map.put(ch, new Node(ch));} else {Node node = map.get(ch);node.freq++;}//方法引用// Node node = map.computeIfAbsent(ch, Node :: new);// node.frea++;}for(Node node : map.values()) {System.out.println(node.toString());}2.构造树PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.ComparingInt(Node::getFreq));queue.offerAll(map.values());while (queue.size() >= 2) {Node x = queue.poll();Node y = queue.poll();int f = x.freq + y.freq;queue.offer(new Node(f, x, y));}root = queue.poll();System.out.println(root);// 功能3 计算每个字符编码 //功能4 字符串编码后占几个bitint sum = dfs(root, new StringBuilder()); // 得到字符串编码后占的bitfor(Node node : map.values()) {System.out.printlin(node);}System.out.println(sum);}public int dfs(Node node, StringBuilder sb) {int sum = 0;if (node.isLeaf()) {//编码node.node = sb.toString();sum = sb.length() * node.freq;// System.out.println(sb.toString()); } else {sum += dfs(node.left, sb.append("0"));sum += dfs(node.right, sb.append("1"));}if (sb.length() > 0) {sb.deleteCharAt(sb.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();}public String decode(String str) {int i = 0;char[] chars = str.toCharArray();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();}
}
活动选择问题
要在一个会议室举办n个活动
- 每个活动有它们各自的起始和结束时间
- 找出时间上不冲突的活动组合,能够最充分利用会议室(举办的活动次数最多)
public class ActivitySelectionProblem{static class Activity{int index;int start;int end;public Activity(int index, int start, int end) {this.index = index;this.start = start;this.end = end;}public int getEnd() {return end;}@Overridepublic void tostring() {return "Activity(" + index + ")";}}public static void main(String[] args) {Activity[] activity = new Activity[]{new Activity(0, 1, 3),new Activity(1, 2, 4),new Activity(2, 3, 5)} Arrays.sort(activity, Comparator.comparingInt(Activity::getEnd))System.out.println(activity);// select(activity, activity.length);}public void select(Activity[] activity, int n) {List<int[]> res = new ArrayList<>();res.add(activity[0]);Activity pre = res;for(int i = 1; i < n; i++) {Activity curr = activity[i];if (curr.start >= pre.end) {res.add(curr);pre = curr;}}for(Activity a : res) {System.out.println(a);}}
}
Leetcode435
无重叠区间
public class Leetcode435{public int eraseOverlapIntervals(int[][] intervals) {// 根据数组中的第二个元素先升序排序Arrays.sort(intervals, (a, b) -> a[1] - b[1]);List<int[]> res = new ArrayList<>();res.add(intervals[0]);int[] pre = res.get(0);int count = 0; // 减少个数for(int i = 1; i < intervals.length; i++) {int[] curr = intervals[i];if (curr[0] < pre[1]) { // 当前的初始值小于前一个的结束值,有冲突count++;} else { // 只要当前的初始值大于等于前一个的结束值,则不冲突res.add(curr);pre = curr;}}return count;}
}
分数背包问题
- n个液体物品,有重量和价格属性
- 现取走10L物品
- 每次可以不拿,全拿,拿一部分,问最高价值是多少
public class FractionalKnapsackProblem{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 perValue() {return value / weight;}@Overridepublic void 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),}select(items, 10);}public int select(Item[] items, int n) {Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());int sum = 0;for(int i = 0; i < items.length; i++) {Item curr = items[i];if (n >= curr.weight) {n -= curr.weight;sum += curr.value;} else {sum += curr.perValue() * n;break;}}return sum;}
}
0-1背包问题
- n个物体都是固体,有重量和价值
- 现取走不超过10克物品
- 每次可以不拿或者全拿,问最高价值是多少
public class FractionalKnapsackProblem{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 perValue() {return value / weight;}@Overridepublic void 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);}public int select(Item[] items, int n) {Arrays.sort(items, Comparator.comparingInt(Item::preValue).reverse());int sum = 0;for(int i = 0; i < items.length; i++) {Item curr = items[i];if (n >= curr.weight) {n -= curr.weight;sum += curr.value;}}return sum;}
}
得到的结果,最大价值结果是:1001630
,实际上选择钻石和红宝石 得到的价值结果 1002400