Java算法学习12——经典问题的DFS和BFS

import java.util.Arrays;
import java.util.linkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Vector;


public class _dfsNbfs {

//DFS1:从n个物品中选择在给定重量中价值最高的
	static int n;//物品总数
	static int maxn=30;//最大物品数
	static int []w=new int [maxn];static int []v=new int [maxn];//物品所对应的重量和价值
	static int sumw,sumv,finalsumv,maxw;
	static void DFS(int index,int sumw,int sumv) {
		if(index==n) {
			if(sumv>finalsumv) {
				finalsumv=sumv;
			}
			return;//已经完成对n个物品的选择
		}else {
			DFS(index+1,sumw,sumv);//不选择这个
			if(sumw+w[index]<=maxw) {
				DFS(index+1,sumw+w[index],sumv+v[index]);
			}
		}
	}
//DFS2:从N个整数中选择K个数的所有方案，这个K个数的和为X
	static int []A=new int [maxn];//存储原始的无序数组
	static Vectortemp;//存储最佳方案
	static Vector ans;
	static int x=0,k=0;//需要满足的和值
	static int sumSqumax=0;//时刻要更新的最大和值
	static void DFS2(int index,int nowk,int sumn,int sumSqu) {
		if(nowk==n&&sumn==x)//个数为k且总数为x 
		{
			if(sumSqu>sumSqumax) {
				sumSqumax=sumSqu;
				ans=temp;
			}
		}
		if(n==index||nowk>k||sumn>x) {
			return;
		}
		temp.add(A[index]);//选了
		DFS2(index+1,nowk+1,sumn+A[index],sumSqu+A[index]*A[index]);
		//如果是可以重复选，则上一步就要改成：
		//DFS2(index,nowk+1,sumn+A[index],sumSqu+A[index]*A[index])
		temp.removeElement(A[index]);
		//不选
		DFS2(index+1,nowk+1,sumn,sumSqu);
	}	
	
//BFS1:选取“1”的块数

	static class node{
		int x;
		int y;
		int step;
		node(){}
	}
	static int xz[]= {0,0,1,-1};
	static int yz[]= {-1,1,0,0};
	static boolean inq[][];
	static boolean judge(int x,int y) {
		if(x<0||x>=n||y<0||y>=n) return false;
		else if(inq[x][y]=true) return false;
		else return true;
	}
	static void BFS(int x,int y) {
		Arrays.fill(inq, false);
		Scanner cin=new Scanner(System.in);
		Queueq=new linkedList<>();
		node k=new node();
		k.x=cin.nextInt();k.y=cin.nextInt();
		cin.nextInt();
		q.add(k);
		inq[x][y]=true;
		while(!q.isEmpty()){
			node newnode=q.poll();
			int newx,newy;
			for(int i=0;i<4;i++) {
				newx=newnode.x+xz[i];
				newy=newnode.y+yz[i];
				if(judge(newx,newy)) {
					k.x=newx;k.y=newy;
					q.add(k);
					inq[newx][newy]=true;
				}//PS:如果需要判断块数多少的话，可以在main函数里面判断，即遍历所有的点，然后如果发现inq[i]=false的话就
				//块数+1，然后再进行BFS把这一个点联通块都访问了
			}
		}
	}
	
//BFS2:
	static int BFS2(int x,int y) {
		node T=new node();//终点
		node S=new node();
		S.x=x;S.y=y;
		Queue q=new linkedList<>();
		q.add(S);
		inq[x][y]=true;
		while(!q.isEmpty()) {
			node newnode=q.poll();
			if(newnode.x==T.x&&newnode.y==T.y) {
				return newnode.step;//达到终点的最佳步数
			}
			for(int i=0;i<4;i++) {
				int newx=newnode.x+xz[i];
				int newy=newnode.y+yz[i];
				if(judge(newx,newy)) {
					newnode.x=newx;newnode.y=newy;
					q.add(newnode);
					inq[newx][newy]=true;
				}
				
			}
			
			
		}
		return -1;
	}
	
	public static void main(String []args) {
		Scanner cin=new Scanner(System.in);
		n=cin.nextInt();maxw=cin.nextInt();
		for(int i=0;i