贪心算法
概念
贪婪算法（Greedy）的定义：是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法
由于贪心算法的高效性以及所求得答案比较接近最优结果，贪心算法可以作为辅助算法或解决一些要求结果不特别精确的问题
注意：当下是最优的，并不一定全局是最优的。举例如下：
有硬币分值为10、9、4若干枚，问如果组成分值18，最少需要多少枚硬币？
采用贪心算法，选择当下硬币分值最大的：10
18-10=8
8/4=2
即：1个10、2个4，共需要3枚硬币
实际上我们知道，选择分值为9的硬币，2枚就够了
18/9=2
如果改成：
有硬币分值为10、5、1若干枚，问如果组成分值16，最少需要多少枚硬币？
采用贪心算法，选择当下硬币分值最大的：10
16-10=6
6-5=1
即：1个10，1个5，1个1 ，共需要3枚硬币
即为最优解
由此可以看出贪心算法适合于一些特殊的情况，如果能用一定是最优解
经典问题：部分背包
背包问题是算法的经典问题，分为部分背包和0-1背包，主要区别如下：
部分背包：某件物品是一堆，可以带走其一部分
0-1背包：对于某件物品，要么被带走（选择了它），要么不被带走（没有选择它），不存在只带走一部分的情况
部分背包问题可以用贪心算法求解，且能够得到最优解
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，可以带走某件物品的一部分，请问：他应该选择哪些物品？
假设背包可容纳50Kg的重量，物品信息如下表：
贪心算法的关键是贪心策略的选择
将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略，单位重量的价值排序： 物品A > 物品B > 物品C
因此，我们尽可能地多拿物品A，直到将物品1拿完之后，才去拿物品B，然后是物品C 可以只拿一部分…..
package com.rubin.algorithm.greedy;
public class Goods {
private String name; //名称
private double weight; //重量
private double price; //价格
private double value; //价值
public Goods(String name, double weight, double price) {
this.name = name;
this.weight = weight;
this.price = price;
this.value=price/weight;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public double getWeight() {
return weight;
}
public void setWeight(double weight) {
this.weight = weight;
}
public double getPrice() {
return price;
}
public void setPrice(double price) {
this.price = price;
}
public double getValue() {
return value;
}
public void setValue(double value) {
this.value = value;
}
}
package com.rubin.algorithm.greedy;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
/**
* 背包问题
* 贪心算法实现
*
* 在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)
*
* 优点：性能高，能用贪心算法解决的往往是最优解
* 缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
*/
public class Bag {
private double maxWeight;
public Bag(double maxWeight) {
this.maxWeight = maxWeight;
}
public void take(List<Goods> goods) {
goods = goods.stream().sorted(Comparator.comparingDouble(Goods::getValue).reversed()).collect(Collectors.toList());
double sumWeight = 0.00;
for (Goods good : goods) {
sumWeight += good.getWeight();
if (sumWeight < maxWeight) {
System.out.println(good.getName() + "取" + good.getWeight() + "kg");
} else {
System.out.println(good.getName() + "取" + (good.getWeight() - sumWeight + maxWeight) + "kg");
return;
}
}
}
public static void main(String[] args) {
Bag bag = new Bag(50);
Goods g1 = new Goods("A", 10, 60); //6
Goods g2 = new Goods("B", 20, 100); //5
Goods g3 = new Goods("C", 30, 120); //4
Goods[] goods = {g1, g2, g3}; // 价值倒序
bag.take(Arrays.asList(goods));
}
}
时间复杂度
在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)
优缺点
优点：性能高，能用贪心算法解决的往往是最优解
缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的
适用场景
针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大
每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）
大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明
在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解
分治算法
概念
分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解
关于分治和递归的区别：分治算法是一种处理问题的思想，递归是一种编程技巧
分治算法的递归实现中，每一层递归都会涉及这样三个操作：
- 分解：将原问题分解成一系列子问题
- 解决：递归地求解各个子问题，若子问题足够小，则直接求解
- 合并：将子问题的结果合并成原问题
比如：
将字符串中的小写字母转化为大写字母
“abcde”转化为"ABCDE"
我们可以利用分治的思想将整个字符串转化成一个一个的字符处理
经典问题
求X的n次幂的问题，比如：
2^10 2的10次幂
一般的解法是循环10次
public static int commpow(int x,int n){
int s=1;
while(n>=1){
s*=x;
n--;
}
return s;
}该方法的时间复杂度是：O(n)
采用分治法
package com.rubin.algorithm.ra;
/**
* 求x的n次方
* 使用分治算法来算
* T = O(logn)
*/
public class HalfPow {
public static int halfPow(int x, int n) {
if (n == 1) {
return x;
}
int half = halfPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public static void main(String[] args) {
System.out.println(halfPow(5, 4));
}
}
时间复杂度
根据拆分情况可以是O(n)或O(logn)
优缺点
优势：将复杂的问题拆分成简单的子问题，解决更容易，另外根据拆分规则，性能有可能提高
劣势：子问题必须要一样，用相同的方式解决
适用场景
分治算法能解决的问题，一般需要满足下面这几个条件：
- 原问题与分解成的小问题具有相同的模式
- 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别
- 具有分解终止条件，也就是说，当问题足够小时，可以直接求解
- 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了
回溯算法
概念
回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径
回溯的处理思想，有点类似枚举（列出所有的情况）搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走
经典问题
N皇后问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击
我们把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，我们不停地检查当前放法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种放法，继续尝试
代码如下：
package com.rubin.algorithm.back;
/**
* n皇后问题
* <p>
* 使用回溯算法
*/
public class NQueen {
private static final int QUEENS = 8;
//下标表示行,值表示queen存储在哪一列
private static final int[] result = new int[QUEENS];
public static void setQueens(int row) {
if (row >= QUEENS) {
print();
return;
}
for (int col = 0; col < QUEENS; col++) {
if (isOK(row, col)) {
result[row] = col;
setQueens(row + 1);
}
}
}
/**
* 判断是否OK的标准 同一行上方、左上角、右下角不能有皇后
*
* @param row
* @param col
* @return
*/
private static boolean isOK(int row, int col) {
int leftup = col - 1;//左对角线
int rightup = col + 1;//右对角线
for (int i = row - 1; i >= 0 ; i--) {
if (result[i] == col) {
return false;
}
if (leftup >= 0) {
if (result[i] == leftup) {
return false;
}
}
if (rightup < QUEENS) {
if (result[i] == rightup) {
return false;
}
}
leftup--;
rightup++;
}
return true;
}
private static void print() {
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
if (result[i] == j) {
System.out.print("Q|");
} else {
System.out.print("*| ");
}
}
System.out.println();
}
System.out.println("-------------------");
}
public static void main(String[] args) {
setQueens(0);
}
}
时间复杂度
N皇后问题的时间复杂度为：O(n!) 实际为 n!/2
优缺点
优点：回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率
劣势：效率相对于低
适用场景
回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了
动态规划
概念
动态规划(Dynamic Programming)，是一种分阶段求解的方法
动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决
首先是拆分问题，我的理解就是根据问题的可能性把问题划分成一步一步，这样就可以通过递推或者递归来实现。关键就是这个步骤，动态规划有一类问题就是从后往前推导。有时候我们很容易知道：如果只有一种情况时，最佳的选择应该怎么做，然后根据这个最佳选择往前一步推导，得到前一步的最佳选择，然后就是定义问题状态和状态之间的关系。我的理解是前面拆分的步骤之间的关系，用一种量化的形式表现出来，类似于高中学的推导公式，因为这种式子很容易用程序写出来，也可以说对程序比较亲和(也就是最后所说的状态转移方程式) 。我们再来看定义的下面的两段，我的理解是比如我们找到最优解，我们应该将最优解保存下来，为了往前推导时能够使用前一步的最优解，在这个过程中难免有一些相比于最优解差的解，此时我们应该放弃，只保存最优解，这样我们每一次都把最优解保存了下来，大大降低了时间复杂度
动态规划中有三个重要概念：
- 最优子结构
- 边界
- 状态转移公式（递推方程）dp方程
经典问题
再谈斐波那契数列
优化递归：
通过上边的递归树可以看出在树的每层和上层都有大量的重复计算，可以把计算结果存起来，下次再用的时候就不用再计算了，这种方式叫记忆搜索，也叫做备忘录模式
代码如下：
package com.rubin.algorithm.dp;
/**
* 优化版本 使用备忘录模式
*/
public class FibonacciRecord {
private static final int[] records = new int[20];
public static int findFibonacciItem(int index) {
if (index <= 1) {
return index;
}
if (records[index] == 0) {
records[index] = findFibonacciItem(index -1) + findFibonacciItem(index - 2);
}
return records[index];
}
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.print(findFibonacciItem(i) + " ");
}
}
}
dp方程：
if(i < 2) 则
dp[0] = 0, dp[1] = 1
if(i >= 2) 则
dp[i] = dp[i - 1] + dp[i - 2]
最优子结构： fib[9]=finb[8]+fib[7]
边界：a[0]=0; a[1]=1
dp方程：fib[n]=fib[n-1]+fib[n-2]
实现代码如下：
package com.rubin.algorithm.dp;
/**
* 优化版本 使用方程递推模式
* T = O(n)
*/
public class FibonacciFunction {
public static int findFibonacciItem(int index) {
int[] records = new int[index + 1];
records[0] = 0;
records[1] = 1;
for (int i = 2; i <= index; i++) {
records[i] = records[i-1] + records[i-2];
}
return records[index - 1];
}
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
System.out.print(findFibonacciItem(i) + " ");
}
}
}
0-1背包问题
有n件物品和一个最大承重为W的背包，每件物品的重量是w[i]，价值是v[i]
在保证总重量不超过W的前提下，选择某些物品装入背包，背包的最大总价值是多少？
注意：每个物品只有一件，也就是每个物品只能选择0件或者1件
分析：
假设：W=10，有5件物品，重量和价值如下：
w[1]=2,v[1]=6
w[2]=2,v[2]=3
w[3]=6,v[3]=5
w[4]=5,v[4]=4
w[5]=4,v[5]=6
dp数组的计算结果如下表：
i:选择i件物品 j:最大承重
解法：
dp方程：
如果：
可以选这一件物品
j < w[i]
不选：
dp[i, j] = dp[i - 1, j]
选了：
dp[i, j] = v[i] + dp[i - 1, j - w[i]]
两者取价值最大的数：Max( dp[i - 1, j] , v[i] + dp[i - 1, j - w[i]] )
不可以选这件物品：
j < w[i] 则：
dp[i, j] = dp[i - 1, j]
代码如下：
package com.rubin.algorithm.dp;
/**
* 0-1背包问题
* 有n件物品和一个最大承重为W的背包，每件物品的重量是w[i]，价值是v[i]，在保证总重量不超过W的前提下，选择某些物品装入背包，背包的最大总价值是多少？
* 注意：每个物品只有一件，也就是每个物品只能选择0件或者1件
* <p>
* 分析：
* 假设：W=10，有5件物品，重量和价值如下：
* w[1]=2,v[1]=6
* w[2]=2,v[2]=3
* w[3]=6,v[3]=5
* w[4]=5,v[4]=4
* w[5]=4,v[5]=6
* dp数组的计算结果如下表：
* i\j 0 1 2 3 4 5 6 7 8 9 10
* 0 0 0 0 0 0 0 0 0 0 0 0
* 1 （w[1]=2,v[1]=6） 0 0 6 6 6 6 6 6 6 6 6
* 2（w[2]=2,v[2]=3） 0 0 6 6 9 9 9 9 9 9 9
* 3（w[3]=6,v[3]=5） 0 0 6 6 9 9 9 9 11 11 14
* 4（w[4]=5,v[4]=4） 0 0 6 6 9 9 9 10 11 13 14
* 5（w[5]=4,v[5]=6） 0 0 6 6 9 9 12 12 15 15 15
* i:选择i件物品 j:最大承重
*
* T = O(i*j)
*/
public class BagDP {
public static int maxValue(int[] values, int[] weights, int max) {
if (values == null || weights == null || max <= 0 || values.length == 0 || weights.length == 0) {
return 0;
}
int[][] DP = new int[values.length + 1][max + 1];
for (int i = 1; i <= values.length; i++) {
for (int j = 1; j <= max; j++) {
if (j < weights[i - 1]) {
DP[i][j] = DP[i - 1][j];
} else {
DP[i][j] = Math.max(DP[i - 1][j], values[i - 1] + DP[i - 1][j - weights[i - 1]]);
}
}
}
int maxValue = DP[values.length][max];
int j = max;
for (int i = values.length; i > 0; i--) {
if (DP[i][j] > DP[i - 1][j]) {
System.out.println("选择了：w=" + weights[i - 1] + ",v=" + values[i - 1]);
j -= weights[i - 1];
if (j <= 0) {
break;
}
}
}
return maxValue;
}
public static void main(String[] args) {
int[] values = {60, 30, 50, 40, 60};
int[] weights = {2, 2, 6, 5, 4};
int max = 10;
System.out.println("最大价值是：" + maxValue(values, weights, max));
}
}
此种解法时间复杂度为O(i * j)
使用动态规划四个步骤
- 把当前的复杂问题转化成一个个简单的子问题（分治）
- 寻找子问题的最优解法（最优子结构）
- 把子问题的解合并，存储中间状态
- 递归+记忆搜索或自底而上的形成递推方程(dp方程)
时间复杂度
新的斐波那契数列实现时间复杂度为O(n)
优缺点
优点：时间复杂度和空间复杂度都相当较低
缺点：难，有些场景不适用
适用场景
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题
环形链表问题
给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false
解法：
1、定义快慢两个指针：slow=head; fast=head.next;
2、遍历链表：快指针步长为2：fast=fast.next.next; 慢指针步长为1：slow=slow.next;
3、当且仅当快慢指针重合(slow==fast)，有环，返回true
4、快指针为null，或其next指向null，没有环，返回false，操作结束
代码实现：
package com.rubin.algorithm.ring;
/**
* 链表节点
*/
public class Node {
int id;
String name;
Node next;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
}
package com.rubin.algorithm.ring;
/**
* 判断链表是否有环
*/
public class RingList {
/**
* 判断链表是否有环
* @param head
* @return
*/
public static boolean isRing(Node head){
if(head==null) return false;
//定义快慢指针
Node slow=head; //慢
Node fast=head.next; //快
while(fast!=null&&fast.next!=null){
//追击相遇 有环
if(slow==fast){
return true;
}
fast=fast.next.next; //步长为2
slow=slow.next;//步长为1
}
//无环
return false;
}
public static void main(String[] args) {
Node n1=new Node(1,"张飞");
Node n2=new Node(2,"赵云");
Node n3=new Node(3,"关羽");
Node n4=new Node(4,"黄忠");
Node n5=new Node(5,"狄仁杰");
n1.next=n2;
n2.next=n3;
n3.next=n4;
n4.next=n5;
n5.next=n1;
System.out.println(isRing(n1));
}
}
以上就是本文的全部内容。欢迎小伙伴们积极留言交流~~~
文章评论