알고리즘 "서커스 타워"여기

Question

에 대한은 "크래킹 코딩 인터뷰"책의 문제입니다. 실용적이고 심미적 인 이유로 각 사람은 자신보다 아래에있는 사람보다 짧고 가벼워 야합니다. 서커스에있는 각 사람의 높이와 무게를 감안할 때, 가능한 탑승 인원 수를 계산하는 방법을 작성하십시오.

예 :

입력 :

(ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110) 

출력 :

최장 탑 길이가 6이며, 위에서 아래로 포함한다 : 여기

(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190) 

부터 용액은 책 :

"이 문제를 해결할 때 우리는 그 문제가 실제로 다음과 같은 것을 이해할 수 있습니다.

우리는 항목 쌍의 목록을 가지고 있습니다. . 제 1 및 제 2 항목 모두 비 내림차순으로되도록 상기 긴 시퀀스를 찾기 "

를 I이 예 내놓았다 여기

 {1,1} 
    {3,3} {7,2} 
{6,4} {9,9} {8,5} 

시퀀스의 값은 비에없는 감소하고있는 주문이지만 여전히 유효한 탑입니다. 그리고 같은 항목을 다른 타워로 구성하여 비 감축 순서로 항목을 구성하는 방법을 찾을 수 없습니다. 그런 방법이 없다고 생각합니다. 따라서 솔루션 이 올바르지 않습니다.

누락 된 것이 있습니까?

미리 감사드립니다.

Answer 1

아니요, 값은 증가하지 않습니다. @MooseBoys 코멘트는 귀하의 경우 2 위보다 큰 3 번째 가치의 무게를 말합니다. ({3,3} -> {7,2}, 2 < 3)

문제는 LIS (Longest Increasing subsequence) (DP)의 약간의 변형입니다.

높이를 기준으로 요소를 정렬 한 다음 가장 긴 증가 하위 시퀀스를 적용하여 적용 할 수 있습니다.

아래의 자바 구현을 찾아주세요 : 나는 LIS 문제의 N 평방 구현을 사용하고

class Person implements Comparable<Person> { 
    int height; 
    int weight; 

    public Person(int height, int weight) { 
     this.height = height; 
     this.weight = weight; 
    } 

    @Override 
    public String toString() { 
     return "Person{" + 
       "height=" + height + 
       ", weight=" + weight + 
       '}'; 
    } 

    @Override 
    public int compareTo(Person p) { 
     if(this.height>p.height) { 
      return 1; 
     } else if(this.height < p.height) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

public class CircusTower { 

    public void calculatePeople(Person[] input) { 

     int weightArray[] = new int[input.length]; 
     String[] output = new String[input.length]; 
     for (int i=0;i<input.length;i++) { 
      weightArray[i] = 1; 
      output[i] = input[i].toString() + ""; 
     } 
     int maxLength = 0; 

     for (int i=1;i<input.length;i++) { 
      for (int j=0;j<i;j++) { 
       if(weightArray[j]+1>weightArray[i] && input[i].weight>input[j].weight) { 
        weightArray[i] = weightArray[j] + 1; 
        output[i] = output[j] + " " + input[i].toString(); 
        if(maxLength<weightArray[i]) { 
         maxLength = weightArray[i]; 
        } 
       } 
      } 
     } 

     System.out.println(); 


     for (int i = 0; i < input.length; i++) { 
      if (weightArray[i] == maxLength) { 
       System.out.println("Longest Increasing subsequence - " + output[i] + " of length = " + maxLength); 
      } 
     } 

    } 

    public static void main(String[] args) { 
     CircusTower ct = new CircusTower(); 
     Person p1 = new Person(65,100); 
     Person p2 = new Person(70,150); 
     Person p3 = new Person(56, 90); 
     Person p4 = new Person(75, 190); 
     Person p5 = new Person(60, 95); 
     Person p6 = new Person(68, 110); 

     Person[] array = new Person[]{p1,p2,p3,p4,p5,p6}; 

     Arrays.sort(array); 

     ct.calculatePeople(array); 

    } 

} 

는, U는 nlogn 하나 더 사용할 수 있습니다.

희망을 분명히합니다.