贪婪算法(Greedy)的定义:是一种在每一步选中都采取在当前状态下最好或最优的选择,从而希望 导致结果是全局最好或最优的算法。贪婪算法:当下做局部最优判断,不能回退
背包问题是算法的经典问题,分为部分背包和0-1背包,主要区别如下: 部分背包:某件物品是一堆,可以带走其一部分
0-1背包:对于某件物品,要么被带走(选择了它),要么不被带走(没有选择它),不存在只带走一 部分的情况。
部分背包问题可以用贪心算法求解,且能够得到最优解。
假设一共有N件物品,第 i 件物品的价值为 Vi ,重量为Wi,一个小偷有一个最多只能装下重量为W的背 包,他希望带走的物品越有价值越好,可以带走某件物品的一部分,请问:他应该选择哪些物品?
假设背包可容纳50Kg的重量,物品信息如下表:
物品 重量(kg) 价值(元) 单位重量的价值(元/kg)
A 10 60 6
B 20 100 5
C 30 120 4
贪心算法的关键是贪心策略的选择,
将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品
按照我们的贪心策略,单位重量的价值排序: 物品A > 物品B > 物品C
我们尽可能地多拿物品A,直到将物品1拿完之后,才去拿物品B,然后是物品C 可以只拿一部 分
/** * 物品信息 */ class Goods { String name; double weight; double price; double val; public Goods(String name, double weight, double price) { this.name = name; this.weight = weight; this.price = price; val = price / weight; } } class BagDemo1 { double bag; // 背包的大小 public void take(List<Goods> goodsList) { sortValue(goodsList); double sum_w = 0; for (Goods goods : goodsList) { sum_w += goods.weight; System.out.println(goods.name + "取" + goods.weight + "kg"); if (sum_w > bag) { return; } } } /** * 按照价值排序 * * @param goodsList * @return */ private List<Goods> sortValue(List<Goods> goodsList) { return goodsList; } public static void main(String[] args) { BagDemo1 bd = new BagDemo1(); Goods goods1 = new Goods("A", 10, 60); Goods goods2 = new Goods("B", 20, 100); Goods goods3 = new Goods("C", 30, 120); List<Goods> goodsList = new ArrayList<>(); goodsList.add(goods1); goodsList.add(goods2); goodsList.add(goods3); bd.bag = 50; bd.take(goodsList); } }
时间复杂度
优缺点
分治算法(divide and conquer)的核心思想其实就是四个字,分而治之 ,也就是将原问题划分成 n 个规模较小,并且结构与原问题相似的子问题,递归地解决这些子问题,然后再合并其结果,就得到原 问题的解。
**关于分治和递归的区别 **
是循环10次,该方法的时间复杂度是:O(n)
我们看到每次拆成n/2次幂,时间复杂度是O(logn)
public static int commpow(int x,int n) { if(n==1) return x; int half = commpow(x, n / 2); // 偶次幂 if (n % 2 == 0) { return half * half; } // 奇次幂 return half * half * x; }
回溯的处理思想,有点类似枚举(列出所有的情况)搜索。我们枚举所有的解,找到满足期望的解。为
了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我
们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就
回退到上一个岔路口,另选一种走法继续走。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
package com.wuzx.algorithmicThinking.back; /** * 回溯算法:N皇后问题 */ public class NQueens { int QUEEN S; int[] result; // 下标表示行,值表示queen存储在哪一列 /** * 构建n皇后哦 * * @param n */ public NQueens(int n) { this.QUEENS = n; this.result = new int[n]; } /** * 在对应的行放置 皇后 * * @param row */ public void setQueens(int row) { if (row == QUEENS) { printQueens(); return; } // 在每行一次放置列 for (int col = 0; col < QUEENS; col++) { if (!isOk(row, col)) { continue; } //设置列 result[row] = col; // 开始下一行 setQueens(row + 1); } } public boolean isOk(int row, int col) { int leftup = col - 1; int rightup = col + 1; // 逐行往上考察每一行 for (int i = row - 1; i >= 0; i--) { //列上存在queen if (result[i] == col) return false; //左上对角线存在queen if (leftup >= 0) { if (result[i] == leftup) return false; } //右下对角线存在queen if (rightup < QUEENS) { if (result[i] == rightup) return false; } leftup--; rightup++; } return true; } /** * 打印输出 */ private void printQueens() { for (int i = 0; i < QUEENS; i++) { for (int j = 0; j < QUEENS; 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) { NQueens queens=new NQueens(8); queens.setQueens(0); } }
动态规划(Dynamic Programming),是一种分阶段求解的方法。动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。
动态规划中有三个重要概念:
通过上边的递归树可以看出在树的每层和上层都有大量的重复计算,可以把计算结果存起来,下次再用
的时候就不用再计算了,这种方式叫记忆搜索,也叫做备忘录模式
/** * 斐波那契数列: 递归分治+记忆搜索(备忘录) */ public class Fib2 { //用于存储每次的计算结果 static int[] sub=new int[10]; public static int fib(int n){ if(n<=1) return n; //没有计算过则计算 if(sub[n]==0){ sub[n]=fib(n-1)+fib(n-2); } //计算过直接返回 return sub[n]; } public static void main(String[] args) { System.out.println(fib(9)); } }
dp方程:
最优子结构: fib[9]=finb[8]+fib[7]
边界:a[0]=0; a[1]=1;
dp方程:fib[n]=fib[n-1]+fib[n-2]
/** * 斐波那契数列 自底向上 递推 */ public class Fib3 { public static int fib(int n){ int a[]=new int[n+1]; a[0]=0; a[1]=1; int i; // a[n]= a[n-1]+a[n-2] for(i=2;i<=n;i++){ a[i]=a[i-1]+a[i-2]; } // i已经加1了,所以要减掉1 return a[i-1]; } public static void main(String[] args) { System.out.println(fib(9)); } }
时间复杂度
优缺点
尽管动态规划比回溯算法高效,但是,并不是所有问题,都可以用动态规划来解决。能用动态规划解决
的问题,需要满足三个特征,最优子结构、无后效性和重复子问题。在重复子问题这一点上,动态规划
和分治算法的区分非常明显。分治算法要求分割成的子问题,不能有重复子问题,而动态规划正好相
反,动态规划之所以高效,就是因为回溯算法实现中存在大量的重复子问题