注：使用二分查找的前提是一个有序数组
package Algorithm;
//二分查找的非递归实现
public class BinarySearchNoRecursion {
public static void main(String[] args) {
int[] arr = {3,7,11,46};
int index = binarySearch(arr, 11);
System.out.println(index);
}
public static int binarySearch(int[] arr,int target){
int left= 0;
int right =arr.length-1;
while (left<=right){
int mid = (left+right)/2;//非递归时mid应放在while中，不断更新自身的值
if (target == arr[mid]){
return mid;
}
else if (target
二、分治算法
汉诺塔问题：将其看作2部分：上面n-1个盘看作1部分，最下面的盘单独看做一部分
package Algorithm.Dac;
//汉诺塔问题
public class Hanoitower {
public static void main(String[] args) {
han(3,'A','B','C');
}
//
public static void han(int nums ,char a,char b,char c){
if (nums==1){
System.out.println("第1个盘从"+a+"->"+c);//此处的a到c，可以理解为起始点到目标点
}
else {
//把上面的盘移动到b
han(nums-1,a,c,b);
//把最下面的盘移动到c
// han(1,a,b,c);//可以用这句辅助理解
System.out.println("第"+nums+"个盘从"+a+"->"+c);
//把b上所有的盘移动到c
han(nums-1,b,a,c);
}
}
}
三、动态规划算法
结合下图方便理解公式
同一列，背包容量相同，但是可供的选择越来越多，因此不断优化组合来达到最大价值
package Algorithm.Dynamic;
//背包问题
public class Knapsack {
public static void main(String[] args) {
int[] w = {1,4,3};//物品的重量
int[] val = {1500,3000,2000};//物品的价值
int m = 4;//背包的容量
int n = val.length;//物品的个数
//对应的价值表，之所以行和列都要+1是第一行和第一列都是0（此处是为了保障公式中的i-1不越界）
int[][] v = new int[n+1][m+1];//v[i][j]表示再前i个物品能够装入容量为j的背包的最大价值
//通过一个和表等大小的二维数组来记录最优解的路径
int[][] path = new int[n+1][m+1];
//初始化第一行和第一列
for (int i = 0; i < v.length; i++) {
v[i][0]=0;
}
for (int j = 0; j < v[0].length; j++) {
v[0][j] =0;
}
//动态规划处理
for (int i = 1; i < v.length; i++) {//不处理第一行
for (int j = 1; j < v[0].length; j++) {//不处理第一列
//公式
if (w[i-1]>j){//因为我们程序是从1开始的，所以公式中的w[i]修改成w[i-1]，下面else中的改动同理;
//因为只是二维数组v的一行一列不处理，所以索引涉及到val和w两个一维数组时要进行-1处理，公式中v本身的索引不变化
//当新增物品的容量大于背包容量时，取上一个单元格的装入策略
v[i][j] = v[i-1][j];
} else {
// v[i][j] = Math.max(v[i-1][j],val[i-1]+v[i-1][j-w[i-1]]);
if (v[i-1][j]0&&j>0){
if (path[i][j]==1){
System.out.println("第"+i+"个商品放入背包");
j-=w[i-1];
}
i--;
}
//先把定位放在了最后一个单元格，也是我们想去求的，包含了容量=4和3种物品都在选择范围内的这一情况，如果此时path=1，说明最后的那种商品是在里面的，
//然后背包的剩余容量就是4-电脑（3），【我们就去j=1的那一列看是否有物品能够放入背包的情况（吉他和音响）】，中括号里面的话等价于：j=4-电脑时path是否=1，
//这一行没有就去上一行找（i--）
}
}
