“马戏团塔”的算法

Question

这是《破解编码面试》一书中的问题：

\n\n

马戏团正在设计一种塔式表演，由人们相互站立\xe2\x80\x99s\n肩膀组成。出于实用和美观的原因，每个人都必须比他或她下面的人矮且轻。给定马戏团中每个人的身高和体重，编写一个方法来计算这样一座塔中的最大可能人数。

\n\n

例子：

\n\n

输入：

\n\n

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

\n\n

输出：

\n\n

最长的塔长 6，从上到下包括：

\n\n

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

\n\n

这是书上的解决方案：

\n\n

“当我们剔除这个问题的所有废话时，我们就能明白问题实际上是以下这样的。

\n\n

我们有一个成对的项目列表。找到最长的序列，使得第一项和第二项都按非递减顺序排列。”

\n\n

我想出了这个例子：

\n\n

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

\n\n

在这里，序列的值不是按非递减顺序排列的，但它仍然是一个有效的塔。而且我找不到一种方法将相同的物品组织到另一个塔中，该塔的物品按非递减顺序排列。我相信没有这样的办法。所以在我看来，这个解决方案是不正确的。

\n\n

我错过了什么吗？

\n\n

提前致谢。

\n

Answer 1

不，您的值不是按非递减顺序排列的。正如 @MooseBoys 评论所说，在你的情况下，第三个值的权重大于第二个值。({3,3} -> {7,2}, 2<3)

该问题是最长递增子序列 (LIS) (DP) 的轻微变化。

您可以根据高度对元素进行排序，然后应用根据重量查找最长的递增子序列。

请找到下面的java实现：

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);

    }

}

我正在使用LIS 问题的n 平方实现，您也可以使用nlogn中更好的一个。

希望它能澄清。