叠罗汉
叠罗汉
一贱书生 发表于12个月前
叠罗汉
  • 发表于 12个月前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

/**
 * 功能:有个马戏团正在设计叠罗汉的表演节目,一个人要站在另一个人的肩膀上。出于实际和美观的考虑,在上面的人一定要比下面的人矮一点、轻一点。
 * 已知马戏团每个人的身高和体重,计算叠罗汉最多能够叠几个人。

 */

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:去掉细枝末节,真正的题目是:给定一个列表,每个元素由一对项目组成。找出最长的子序列,其中第一项和第二项均以非递减的顺序排列。 
  3.  * 1、子问题:最长递增子序列:找出以元素i结尾的最长递增子序列。 
  4.  *           以A[i]结尾的最长子序列可以通过检查先前全部解法得出,只要将A[i]附加到最长且“有效”的那个序列即可。有效指A[i]>list.tail的任意序列。 
  5.  * 2、真正的子问题;最长递增子序列,每个元素均为一对数据。 
  6.  * @param items 
  7.  * @return 
  8.  */  
  9. public static ArrayList<Actor> getIncreasingSequence(ArrayList<Actor> items){  
  10.     Collections.sort(items);  
  11.     return longestIncreasingSubsequence(items);  
  12. }  
  13.   
  14. public static ArrayList<Actor> longestIncreasingSubsequence(ArrayList<Actor> array) {  
  15.     // TODO Auto-generated method stub  
  16.     ArrayList<Actor>[] solutions=new ArrayList[array.size()];  
  17.     longestIncresingSubsequence(array,solutions,0);  
  18.       
  19.     ArrayList<Actor> bestSequence=new ArrayList<Actor>();  
  20.     for(ArrayList<Actor> sol:solutions){  
  21.         bestSequence=seqWithMaxLength(bestSequence,sol);  
  22.     }  
  23.       
  24.     return bestSequence;  
  25. }  
  26.   
  27. public static void longestIncresingSubsequence(ArrayList<Actor> array,ArrayList<Actor>[] solutions, int currentIndex) {  
  28.     // TODO Auto-generated method stub  
  29.     if(currentIndex>=solutions.length||currentIndex<0)  
  30.         return;  
  31.       
  32.     Actor currentElement=array.get(currentIndex);  
  33.       
  34.     //找出可以附加currentElement的最长子序列  
  35.     ArrayList<Actor> bestSequence=new ArrayList<Actor>();  
  36.     for(int i=0;i<currentIndex;i++){  
  37.         if(array.get(i).isBefore(currentElement))  
  38.             bestSequence=seqWithMaxLength(bestSequence, solutions[i]);  
  39.     }  
  40.       
  41.     //附加currentElement  
  42.     ArrayList<Actor> newSolution=new ArrayList<Actor>();  
  43.     if(bestSequence!=null)  
  44.         newSolution.addAll(bestSequence);  
  45.     newSolution.add(currentElement);  
  46.       
  47.     //加入到列表中,然后递归  
  48.     solutions[currentIndex]=newSolution;  
  49.     longestIncresingSubsequence(array, solutions, currentIndex+1);  
  50.       
  51. }  
  52.   
  53. //返回较长的序列  
  54. public static ArrayList<Actor> seqWithMaxLength(ArrayList<Actor> seq1, ArrayList<Actor> seq2) {  
  55.     // TODO Auto-generated method stub  
  56.     if(seq1==null)  
  57.         return seq2;  
  58.     if(seq2==null)  
  59.         return seq1;  
  60.     return seq1.size()>seq2.size()?seq1:seq2;  
  61. }  

 

[java] view plain copy

 

  1. class Actor implements Comparable{  
  2.     int height;  
  3.     int weight;  
  4.       
  5.     @Override  
  6.     public int compareTo(Object s) {  
  7.         // TODO Auto-generated method stub  
  8.         Actor second=(Actor) s;  
  9.         if(this.height!=second.height)  
  10.             return ((Integer)this.height).compareTo(second.height);  
  11.         else   
  12.             return ((Integer)this.weight).compareTo(second.weight);  
  13.     }  
  14.       
  15.     public boolean isBefore(Actor other){  
  16.         if(this.height<other.height&&this.weight<other.weight)  
  17.             return true;  
  18.         return false;  
  19.     }  
  20.       
  21. }
共有 人打赏支持
粉丝 14
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: