import java.util.*;
public class RecursionDemo{
/**************************************** SubSequence **************************************/
public static HashSet getSubSequence(String str){
HashSet arr=new HashSet();
subSeqProcess(str.toCharArray(),0,"",arr);
return arr;
}
public static void subSeqProcess(char[] str,int length,String path,HashSet list){
if(str.length ==length){
list.add(path);
return ;
}
char ch = str[length];
subSeqProcess(str,length+1,path,list);
subSeqProcess(str,length+1,path+String.valueOf(ch),list);
}
/**************************************** Permutation *************************************/
public static HashSet getPermutation(String str){
HashSet arr=new HashSet();
ArrayList strArr=new ArrayList();
for (int i=0; i str,String path,HashSet list){
if(str.isEmpty()){
list.add(path);
}else{
int length = str.size();
for (int i=0; i=0; i--) {
for (int rest=0; rest<=bag;rest++ ) {
int p1 = dp[i+1][rest];
int p2=0;
int next = rest-w[i]<0?-1:dp[i+1][rest-w[i]];
if(next != -1){
p2 = v[i]+next;
}
dp[i][rest] = Math.max(p1,p2);
}
}
return dp[0][bag];
}
public static int bag1(int[] w,int[] v,int bag){
return process3(w,v,0,bag);
}
public static int process3(int[] w,int[] v,int index,int rest){
if(rest<0){
return -1;
}
if(index == w.length){
return 0;
}
int p1 = process3(w,v,index+1,rest);
int p2=0;
int next = process3(w,v,index+1,rest-w[index]);
if(next != -1){
p2 = v[index]+next;
}
return Math.max(p1,p2);
}
/**************************************** Cut *************************************/
public static int cut1(int[]w,int[] v,int restLength){
int[] dp = new int[restLength+1];
for (int i=1; i<=restLength; i++) {
int max=0;
for (int j=1; j<=i&&j=0){
max= Math.max(v[j-1]+dp[i-j],max);
}
}
dp[i]=max;
}
System.out.println();
for (int i=0; i<=restLength; i++) {
System.out.print(dp[i]+",");
}
System.out.println();
return dp[restLength];
}
public static int cut(int[]w,int[] v,int restLength){
List list= new ArrayList();
int[] dp = new int[restLength+1];
for (int i=0; i<=restLength; i++) {
dp[i]=-1;
}
int max= process4(w,v,restLength,"",list,dp);
for (String str:list ) {
System.out.println(str);
}
System.out.println();
for (int i=0; i<=restLength; i++) {
System.out.print(dp[i]+",");
}
System.out.println();
return max;
}
public static void f(String path,List list){
if(list.isEmpty()){
list.add(path);
}else{
int x=0;
for (String str: path.split(",") ) {
x+=Integer.valueOf(str);
}
int y=0;
for (String str:list.get(0).split(",") ) {
y+=Integer.valueOf(str);
}
if(x>y){
list.clear();
list.add(path);
}
}
}
public static int process4(int[]w,int[] v,int rest,String path,List list,int[] dp){
if(dp[rest]!=-1){
return dp[rest];
}
if(rest == 0 ){
f(path,list);
return 0;
}
int max=0;
for (int i=1; i<=v.length; i++) {
int r = rest-w[i-1];
if(r>=0){
String p=path+v[i-1]+",";
// System.out.println("path = "+p+"$r="+r);
int p1=v[i-1]+process4(w,v,rest-w[i-1],p,list,dp);
max= Math.max(max,p1);
}
}
dp[rest]= max;
return max;
}
/**************************************** 迷宫 *************************************/
public static boolean migong(int[][] arr,int[] start,int[] end){
int curRow=start[0];
int curClo=start[1];
boolean[] result = new boolean[]{false};
migongProcess(arr,end,curRow,curClo,result);
return result[0];
}
public static void migongProcess(int[][] arr,int[] end,int curRow,int curClo,boolean[] result){
if(result[0]) return;
if(curRow<0 ||curClo<0 || curRow==arr.length || curClo==arr[0].length) return;
if(curRow == end[0] && curClo == end[1] && arr[curRow][curClo] == 0){
result[0]=true;
}
if(arr[curRow][curClo] == 0){
arr[curRow][curClo]=8;
migongProcess(arr,end,curRow,curClo+1,result); //right
migongProcess(arr,end,curRow,curClo-1,result); //left
migongProcess(arr,end,curRow+1,curClo,result); //bottom
migongProcess(arr,end,curRow-1,curClo,result); //top
}
}
public static void migongPrint(){
for (int w=0; w<1000;w++ ) {
int[][] arr= getMatrix(20,20);
int[] start = new int[]{0,0};
int[] end = new int[]{arr.length-1,arr[0].length-1};
boolean r=migong(arr,start,end);
if(r){
for (int i=0;i arr = getSubSequence("acccddeeffccc");
// for (String str : arr ) {
// System.out.println("\""+str+"\"");
// }
// HashSet arr = getPermutation("1114");
// for (String str : arr ) {
// System.out.println("\""+str+"\"");
// }
// System.out.println("count = "+reboot2(5,2,4,100));
// System.out.println("count = "+reboot3(5,2,4,100));
// int[] _arr = getArray();
// int result=win1(_arr);
int[] w=new int[]{1,2,3,4,5};
int[] v=new int[]{1,5,8,9,10};
System.out.println(bag1(w,v,4));
System.out.println(bag2(w,v,4));
// 1 2 3 4 5 6
// int[] w=new int[]{1,2,3,4,5};
// int[] v1=new int[]{2,5,1,9,4};
// System.out.println("max="+cut(w,v1,140));
// System.out.println("max="+cut1(w,v1,140));
//migongPrint();
}
}