package 典型算法题;

import java.util.Arrays;

//背包问题(贪心算法)
public class GreedyPackage {

  private int MAX_WEIGHT = 150;
  private int[] weights = new int[]{35,30,60,50,40,10,25};
  private int[] values = new int[]{10,40,30,50,35,40,30};

  private void packageGreedy(int capacity,int[] weights,int[] values){
          int n = weights.length;
          double[] r = new double[n]; //性价比数组
          int[] index = new int[n];   //按性价比排序物品的下标
          for(int i = 0;i < n;i++){
              r[i] = (double) values[i] / weights[i];
              index[i] = i;//默认排序
      }

      double temp = 0;    //对性价比进行排序
      for(int i = 0;i < n - 1;i++){
          for(int j = i + 1;j < n;j++){
              if(r[i] < r[j]){
                  temp = r[i];
                  r[i] = r[j];
                  r[j] = temp;
                  int x = index[i];
                  index[i] = index[j];
                  index[j] = x;
              }
          }
      }

      //将排序好的重量和价值分别存到数组中
      int[] w1 = new int[n];
      int[] value1 = new int[n];

      for(int i = 0;i < n;i++){
          w1[i] = weights[index[i]];
          value1[i] = values[index[i]];

      }
      int[] x = new int[n];
      int maxValue = 0;
      for(int i = 0;i < n;i++){
          if(w1[i] <= capacity){   //表明还可以装得下
              x[i] = 1;   //表示该物品被装了
              capacity = capacity - w1[i];
              maxValue += value1[i];
          }
      }
      System.out.println("总共放下的物品数量:" + Arrays.toString(x));
      System.out.println("最大价值为:" + maxValue);
  }


  public static void main(String[] args){
      GreedyPackage g = new GreedyPackage();
      g.packageGreedy(g.MAX_WEIGHT,g.weights,g.values);
  }
}

?

三、回溯法

算法定义

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态点称为“回溯点”。

算法原理

回溯法是一种满足某些约束条件的穷举搜索法，他要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行，测试探下一种可能的方法。

解题步骤，

其解题过程主要分为三个步骤，

1. 针对所给问题，定义问题的解空间；

2. 确定易于搜索的解空间结构，

3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

特征和典型的应用场景

回溯是递归的一个特例。但它又有别与一般的递归法，用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根节点到当前扩展节点的路径。

典型应用有：迷宫搜索、N皇后问题、骑士巡游、正则表达式匹配等。

常见应用案例

如一三年蓝桥杯省赛Java组真题“剪格子”就是采用典型的回溯法思想：

package 一三年省赛真题;
 
import java.util.Scanner;
 
public class Year2013_t10 {
 
	static int[][] g;
	static int[][] sign;
	static int m;
	static int n;
	static int s=0;	//记录格子中元素的总和
	static int answer = Integer.MAX_VALUE;	//最终格子数
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		m = scanner.nextInt();		//输入格子的宽
		n = scanner.nextInt();		//输入格子的高
		g = new int[n][m];	
		sign = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				g[i][j] = scanner.nextInt();	//为格子赋值
				s+=g[i][j];
			}
		}
		move(0, 0, 0, 0);
		System.out.println(answer);
	}
	
	/**
	 * 记录格子的遍历过程
	 * @param i 移动的横坐标
	 * @param j 移动的纵坐标
	 * @param step 步数
	 * @param sum 格子中元素的总和
	 * */
	public static void move(int i,int j,int step,int sum) {
		//如果该格子坐标不在范围内，或该格子已经走过，则返回
		if (i==n||i<0||j<0||j==m||sign[i][j]==1) {
			return;
		}
		// 如果当前数值和是总和的一半
		if (sum*2==s) {
			answer = Math.min(answer, step);	//对格子数（步数）与符合要求的格子数比较，取出最小值
		}
		sign[i][j] = 1;		//对走过的格子进行标记，表示格子已经走过
		move(i+1, j, step+1, sum+g[i][j]);	//down
		move(i-1, j, step+1, sum+g[i][j]);	//up
		move(i, j-1, step+1, sum+g[i][j]);	//left
		move(i, j+1, step+1, sum+g[i][j]);	//right
		sign[i][j] = 0;		//将该格子重新置于未走过的状态（回溯算法）
		
	}
 
}

package 一八年省赛真题;
 
import java.util.Random;
 
 
public class Year2018_Bt5 {
 
	public static int quickSelect(int a[],int l,int r,int k) {
		Random rand = new Random();
		int p = rand.nextInt(r-l+1) + l;
		int x = a[p];
		int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
		int i = l, j = r;
		while (i<j) {
			while (i<j&&a[i]<x) i++;
			if (i<j) {
				a[j] = a[i];
				j--;
			}
			while (i<j&&a[j]>x) j--;
			if (i<j) {
				a[i] = a[j];
				i++;
			}
			
		}
		
		a[i] = x;
		p = i;
		if(i - l + 1 == k) return a[i];
		if(i - l + 1 < k) return quickSelect(a, i + 1, r, k - i + l - 1);	//填空
		else return quickSelect(a, l, i - 1, k);
		
	}
	
	public static void main(String[] args) {
		int a[] = {1,4,2,8,5,7};
		//1，2，4，5，7，8
		//输出5
		System.out.println(quickSelect(a, 0, 5, 6));
	}
 
}

public class Year2017_Bt6 {
	
	static int f(String s1,String s2) {
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		
		int [][]a = new int[c1.length+1][c2.length+1];
//		"abcdkkk" 和"baabcdadabc",
		int max = 0;
		//利用循环来进行动态规划，模拟矩阵中的匹配过程
		for (int i = 1; i < a.length; i++) {
			for (int j = 1; j < a[i].length; j++) {
				//如果两个字符匹配成功
				if (c1[i-1]==c2[j-1]) {
					a[i][j] = a[i-1][j-1]+1;	//填空
					//判断当前字符的长度是否大于已经匹配到的串的长度
					if (a[i][j]>max) max=a[i][j];
				}
			}
		}
		return max;	//返回匹配到的最长的字符串
	}
	
	public static void main(String[] args) {
		int n = f("abcdkkk", "baabcdadabc");
		System.out.println(n);
	}
 
}