求助一种递归实现

Question

问题：已知一个数组int[] arr=new int[length]，对里面的数进行一次排列，每一种排列都对应一个具体的适应值（这种值的得到假设用getVlue(int[] arr)方法得到），现在怎么要得到这length! 种排列的适应值的最小值。请问怎么用递归方法实现。不甚感激

Answer 1

不甚感激->不怎么感激
不胜感激->非常感激有区别的。

Answer 2

import java.util.*;
public class Test{
static int min;
    public static void main(String args[])  {
     int[] arr={4,1,8,5};
     min=getValue(arr);
     minPermutation(arr,0);
     System.out.println("min="+min);    }
    //随便写的一个getVlale().
    public static int getValue(int[] a){
     int value=0;
     for(int i=0;i<a.length;i+=2){ //求偶下标元素之和.
     value+=a[i];
     }
     if(value%2==0){               //这里也可以用位运算.
     value<<=1;                //如果偶下标之和为偶数就除2.
     }
     int value2=0;
     for(int i=1;i<a.length;i+=2){  //求奇下标元素之和.
     value2+=a[i];         
     }
     if(value2%2!=0){               //如果奇下标元素之和为奇数就乘2.
     value2<<=1;          
     }
     return value+value2;
    }
    //递归求全排列.
    public static void minPermutation(int[] a,int index){
     if(index==a.length-1){
     System.out.print(Arrays.toString(a));
     int value=getValue(a);
     System.out.println(" value="+value);
     if(value<min){
     min=value;
     }
     }
     int temp;
     for(int i=index;i<a.length;i++){
     temp=a[index];
     a[index]=a[i];
     a[i]=temp;
     minPermutation(a,index+1);
     temp=a[index];
     a[index]=a[i];
     a[i]=temp;
     }
    }
}F:\java>java Test
[4, 1, 8, 5] value=30
[4, 1, 5, 8] value=27
[4, 8, 1, 5] value=31
[4, 8, 5, 1] value=27
[4, 5, 8, 1] value=30
[4, 5, 1, 8] value=31
[1, 4, 8, 5] value=27
[1, 4, 5, 8] value=24
[1, 8, 4, 5] value=31
[1, 8, 5, 4] value=24
[1, 5, 8, 4] value=27
[1, 5, 4, 8] value=31
[8, 1, 4, 5] value=30
[8, 1, 5, 4] value=23
[8, 4, 1, 5] value=27
[8, 4, 5, 1] value=23
[8, 5, 4, 1] value=30
[8, 5, 1, 4] value=27
[5, 1, 8, 4] value=23
[5, 1, 4, 8] value=27
[5, 8, 1, 4] value=24
[5, 8, 4, 1] value=27
[5, 4, 8, 1] value=23
[5, 4, 1, 8] value=24
min=23

Answer 3

如果是求全排列 我给你一个public class T {
public static void go(int[] data, boolean[] state, int[] flag, int p) {
if (p >= data.length) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[flag[i]] + " ");
}
System.out.println();
return;
} for (int i = 0; i < data.length; i++) {
if (!state[i]) {
state[i] = true;
flag[p] = i;
go(data, state, flag, p + 1);
state[i] = false;
}
}
} public static void go(int[] data) {
boolean[] state = new boolean[data.length];
int[] flag = new int[data.length];
go(data, state, flag, 0);
} public static void main(String[] args) {
int[] data = { 1, 2, 3, 4 };
go(data);
}
}