9.11並べ替えと検索(七)——畳羅漢
/**
* 機能:あるサーカス団が羅漢を畳むショー番組を設計していて、一人がもう一人の肩に立っています.実際と美観の考慮から、上の人は必ず下の人より少し低く、軽くしなければならない.
* サーカスは一人一人の身長と体重が知られており、畳羅漢は最大数人を畳むことができると計算されている.
*/
* 機能:あるサーカス団が羅漢を畳むショー番組を設計していて、一人がもう一人の肩に立っています.実際と美観の考慮から、上の人は必ず下の人より少し低く、軽くしなければならない.
* サーカスは一人一人の身長と体重が知られており、畳羅漢は最大数人を畳むことができると計算されている.
*/
/**
* ： ， ： ， 。 ， 。
* 1、 ： ： i 。
* A[i] ， A[i] “ ” 。 A[i]>list.tail 。
* 2、 ； ， 。
* @param items
* @return
*/
public static ArrayList<Actor> getIncreasingSequence(ArrayList<Actor> items){
Collections.sort(items);
return longestIncreasingSubsequence(items);
}
public static ArrayList<Actor> longestIncreasingSubsequence(ArrayList<Actor> array) {
// TODO Auto-generated method stub
ArrayList<Actor>[] solutions=new ArrayList[array.size()];
longestIncresingSubsequence(array,solutions,0);
ArrayList<Actor> bestSequence=new ArrayList<Actor>();
for(ArrayList<Actor> sol:solutions){
bestSequence=seqWithMaxLength(bestSequence,sol);
}
return bestSequence;
}
public static void longestIncresingSubsequence(ArrayList<Actor> array,ArrayList<Actor>[] solutions, int currentIndex) {
// TODO Auto-generated method stub
if(currentIndex>=solutions.length||currentIndex<0)
return;
Actor currentElement=array.get(currentIndex);
// currentElement
ArrayList<Actor> bestSequence=new ArrayList<Actor>();
for(int i=0;i<currentIndex;i++){
if(array.get(i).isBefore(currentElement))
bestSequence=seqWithMaxLength(bestSequence, solutions[i]);
}
// currentElement
ArrayList<Actor> newSolution=new ArrayList<Actor>();
if(bestSequence!=null)
newSolution.addAll(bestSequence);
newSolution.add(currentElement);
// ，
solutions[currentIndex]=newSolution;
longestIncresingSubsequence(array, solutions, currentIndex+1);
}
//
public static ArrayList<Actor> seqWithMaxLength(ArrayList<Actor> seq1, ArrayList<Actor> seq2) {
// TODO Auto-generated method stub
if(seq1==null)
return seq2;
if(seq2==null)
return seq1;
return seq1.size()>seq2.size()?seq1:seq2;
}class Actor implements Comparable{
int height;
int weight;
@Override
public int compareTo(Object s) {
// TODO Auto-generated method stub
Actor second=(Actor) s;
if(this.height!=second.height)
return ((Integer)this.height).compareTo(second.height);
else
return ((Integer)this.weight).compareTo(second.weight);
}
public boolean isBefore(Actor other){
if(this.height<other.height&&this.weight<other.weight)
return true;
return false;
}
}