1) 贪心例子
称之为贪心算法或贪婪算法，核心思想是
将寻找最优解的问题分为若干个步骤
每一步骤都采用贪心原则，选取当前最优解
因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优
v2已经不会更新v3因为v3更新过了
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。
贪心算法的应用：
背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。
活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。
编辑距离问题：给定两个字符串，求它们之间的最小编辑距离(即将一个字符串转换为另一个字符串所需的最少操作次数)。
网络流问题：给定一张有向图和一些起点和终点，求最大流量。
找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。
常见问题及解答：
贪心算法一定会找到最优解吗？ 答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。
如何判断一个问题是否适合用贪心算法解决？ 答：一个问题如果可以用递归的方式分解成若干个子问题，且每个子问题都有明确的最优解(即局部最优),那么这个问题就可以用贪心算法解决。
贪心算法的时间复杂度是多少？ 答：贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说，对于规模较小的问题，贪心算法的时间复杂度可以达到O(nlogn)或O(n^2);对于规模较大的问题，可能需要O(n^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
任务编排
求复杂问题的近似解
2) 零钱兑换问题
有几个解（零钱兑换 II）Leetcode 518
[1,2,5] 5 暴力递归
有解：[1, 1, 1, 1, 1]
无解：[1, 1, 1, 1, 2]
无解：[1, 1, 1, 1, 5]
有解：[1, 1, 1, 2]
无解：[1, 1, 1, 5]
无解：[1, 1, 2, 2]
无解：[1, 1, 2, 5]
无解：[1, 1, 5]
有解：[1, 2, 2]
无解：[1, 2, 5]
无解：[1, 5]
无解：[2, 2, 2]
无解：[2, 2, 5]
无解：[2, 5]
有解：[5]
4
public int rec(int index,int[] coins,int remainder){
//1.情况1:剩余金额 < 0 - 无解
//2.情况2:剩余金额 > 0 - 继续递归
//3.情况3:剩余金额 = 0 - 有解
if(remainder < 0){
return 0;
}
else if(remainder == 0){
return 1;
}
else{
int count = 0;
for(int i = index;i<coins.length;i++){
count+=rec(i,coins,remainder-coins[i]);
}
return count;
}
}那这个递归是怎么运作的呢?
/*
//第一次传入 index= 0=>1 处理硬币和剩余金额
rec(1,5) remainder > 0 所以走else逻辑 再循环中的递归是多路递归
rec(1,4)
rec(1,3)
rec(1,2)
rec(1,1)
rec(1,0) <== 1
rec(2,-1) <== 0
rec(5,-4) <== 0
rec(2,0) <==1
rec(5,-3) <== 0
rec(2,1)
rec(2,-1) <== 0
rec(5,-4) <== 0
rec(5,-2) <== 0
rec(2,2)
rec(2,0) <== 1
rec(5,-3) <== 0
rec(5,-1) <== 0
rec(2,5-2=3)
rec(2,1)
rec(2,-1) <== 0
rec(5,-4) <== 0
rec(5,-2) <==0
rec(5,5-5=0) < ==1
*/
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
/**
* 零钱兑换
* 可以凑成总金额所需的所有组合可能数
*/
public class Leetcode518 {
public int coinChange(int[] coins, int amount) {
return rec(0, coins, amount, new LinkedList<>(), true);
}
/**
* 求凑成剩余金额的解的个数
*
* @param index 当前硬币索引
* @param coins 硬币面值数组
* @param remainder 剩余金额
* @param stack -
* @param first -
* @return 解的个数
*/
public int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first) {
if(!first) {//第一次不压栈
stack.push(coins[index]);
}
// 情况1：剩余金额 < 0 - 无解
int count = 0;
if (remainder < 0) {
print("无解：", stack);
// if(!stack.isEmpty()){
// stack.pop();
// }
}
// 情况2：剩余金额 == 0 - 有解
else if (remainder == 0) {
print("有解：", stack);
// if(!stack.isEmpty()){
// stack.pop();
// }
count = 1;
}
// 情况3：剩余金额 > 0 - 继续递归
else {
for (int i = index; i < coins.length; i++) {
count += rec(i, coins, remainder - coins[i], stack, false);
}
}
if (!stack.isEmpty()) {
stack.pop();
}
return count;
}
private static void print(String prompt, LinkedList<Integer> stack) {
ArrayList<Integer> print = new ArrayList<>();
ListIterator<Integer> iterator = stack.listIterator(stack.size());
while (iterator.hasPrevious()) {
print.add(iterator.previous());
}
System.out.println(prompt + print);
}
public static void main(String[] args) {
Leetcode518 leetcode = new Leetcode518();
// int count = leetcode.coinChange(new int[]{1, 5, 10, 25}, 41);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);
// int count = leetcode.change(new int[]{15, 10, 1}, 21);
System.out.println(count);
}
}但是这个代码放在leetcode上面跑会超时,因为重复处理了很多次相同的操作
我们可以考虑用记忆法 & 动态规划来优化
我们也可以考虑顺序优化 ==>规模下降明显
/*
[5,2,1] 5
rec(5,5)
rec(5,0) <== 1
rec(2,3)
rec(2,1)
rec(2,-1) <==0
rec(1,0) <==1
rec(1,1)
rec(1,0) <==1
rec(1,4)
rec(1,3)
rec(1,2)
rec(1,1)
rec(1,0) <==1
*/
但即使是这样写在leetcode上也是会 StackOverflowError
class Solution {
public int change(int amount, int[] coins1) {
int[] coins = sort(coins1);
return rec(0,coins,amount);
}
int rec(int index,int[] coins,int remainder){
int count = 0;
if(remainder == 0){
return 1;
}else if(remainder<0){
return 0;
}else{
for(int i = index;i<coins.length;i++){
count+=rec(index,coins,remainder);
}
return count;
}
}
/**
*传入一个有序的数组a(从小到大排序),返回一个从大到小的数组
*@param a 传入的数组(有序)
*@return 返回一个数组(从大到小)
*/
int[] sort(int[] a){
int[] temp = a;
if(temp.length % 2 ==0){
//数组里面的个数为偶数
for(int i = 0;i<=temp.length/2;i++){
int temp1 = a[i];
temp[i] = temp[temp.length-1-i];
temp[temp.length-1] = temp1;
}
}else{
//数组里面的个数为奇数
for(int i = 0;i<temp.length/2;i++){
int temp1 = a[i];
temp[i]=temp[temp.length-1-i];
temp[temp.length-1-i] = temp1;
}
}
return temp;
}
}import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = sort(new int[]{1,2,3});
System.out.println(Arrays.toString(arr));
//为什么我这么选择是因为用Arrays.sort要将数组转化为Integer[]
}
/**
*传入一个有序的数组a（从小到大排序），返回一个从大到小的数组
* @param a 传入的数组（有序）
* @return 返回一个数组（从大到小）
*/
public static int[] sort(int[] a){
int[] temp = a;
if(temp.length%2==0){
//数组里面的个数为偶数
for (int i = 0; i <= temp.length/ 2; i++) {
int temp1 = a[i];
temp[i]=temp[temp.length-1-i];
temp[temp.length - 1-i] = temp1;
}
}else{
//数组里面的个数为奇数
for (int i = 0; i < temp.length / 2; i++) {
int temp1 = a[i];
temp[i]=temp[temp.length-1-i];
temp[temp.length - 1-i] = temp1;
}
}
return temp;
}
}动态规划->会在动态规划章节说明
最优解（零钱兑换）- 穷举法 Leetcode 322
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;
public class Leetcode322 {
static int min = -1; // 需要的最少硬币数 2 3
public int coinChange(int[] coins, int amount) {
rec(0, coins, amount, new AtomicInteger(-1), new LinkedList<>(), true);
return min;
}
// count 代表某一组合 钱币的总数 可变的整数对象
public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack, boolean first) {
if (!first) {
stack.push(coins[index]);
}
count.incrementAndGet(); // count++
if (remainder == 0) {
System.out.println(stack);
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, stack, false);
}
}
count.decrementAndGet(); // count--
if (!stack.isEmpty()) {
stack.pop();
}
}
public static void main(String[] args) {
Leetcode322 leetcode = new Leetcode322();
// int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{2}, 3);
// int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);
System.out.println(count);
}
}最优解（零钱兑换）- 贪心法 Leetcode 322
自己看看就行因为有些测试样例过不了
假定传过来的数据就是从大到小排序,因为java对int数组从大到小排序比较麻烦
public class Leetcode322 {
public int coinChange(int[] coins, int amount) {
int remainder = amount;
int count = 0;
for (int coin : coins) {
while (remainder - coin > 0) {
remainder -= coin;
count++;
}
if (remainder - coin == 0) {
remainder = 0;
count++;
break;
}
}
if (remainder > 0) {
return -1;
} else {
return count;
}
}
public static void main(String[] args) {
Leetcode322 leetcode = new Leetcode322();
int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{2}, 3);
// 问题1 没有回头，导致找到更差的解
// int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);
// 问题2 没有回头，导致无解
// int count = leetcode.coinChange(new int[]{15, 10}, 20);
System.out.println(count);
}
}
