algorithm - 在这样的塔中找到尽可能多的人

Question

首先，让我们来看问题，

一个马戏团正在设计一个塔套路，其中的人站在彼此的塔顶上肩膀。出于实用和审美的原因，每个人都必须比他或她下面的人既矮又轻。给定马戏团中每个人的高度和体重，编写一个方法来计算最大可能人数在这样的塔里。

EXAMPLE:
Input:
        (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: 
        (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

但是我不太明白解决方法如下:

书中提出的解决方案:

• 第 1 步。按高度对所有项目进行排序首先，然后按重量。这意味着如果所有的高度都是独一无二的然后项目将排序他们的高度。如果高度是同样，项目将按他们的排序重量。示例:»»排序前:(60, 100) (70, 150) (56, 90) (75,190) (60, 95) (68,110)。 “后排序:(56, 90), (60, 95),(60,100), (68, 110), (70,150),(75,190).

• 第 2 步。找到最长的序列其中包含不断增加的高度和增加权重。为此，我们:

• a) 从
  开始顺序。目前，max_sequence 是空。

• b) 如果对于下一项，
  高度体重不大于比上一项，我们
  将此项标记为“不适合”

  c) 如果找到的序列的项目多于“最大序列”，它变成“最大顺序”。

• d) 之后搜索是从“不合适的项目”重复，
  直到我们到达尽头
  原始序列。

  public class Question {
  ArrayList<HtWt> items;
  ArrayList<HtWt> lastFoundSeq;
  ArrayList<HtWt> maxSeq;
  
  
  / Returns longer sequence
  ArrayList<HtWt> seqWithMaxLength(ArrayList<HtWt> seq1, ArrayList<HtWt> seq2) {
      return seq1.size() > seq2.size() ? seq1 : seq2;
  }
  
  
  // Fills next seq w decreased wts&returns index of 1st unfit item.
  int fillNextSeq(int startFrom, ArrayList<HtWt> seq) {
    int firstUnfitItem = startFrom;
    if (startFrom < items.size()) {
        for (int i = 0; i < items.size(); i++) {
          HtWt item = items.get(i);
          if (i == 0 || items.get(i-1).isBefore(item)) {
              seq.add(item);
          } else {
              firstUnfitItem = i;
          }
        }
    }
    return firstUnfitItem;
  }
  
  
  // Find the maximum length sequence
  void findMaxSeq() {
    Collections.sort(items);
    int currentUnfit = 0;
    while (currentUnfit < items.size()) {
        ArrayList<HtWt> nextSeq = new ArrayList<HtWt>();
        int nextUnfit = fillNextSeq(currentUnfit, nextSeq);
        maxSeq = seqWithMaxLength(maxSeq, nextSeq);
        if (nextUnfit == currentUnfit) 
          break;
        else 
          currentUnfit = nextUnfit;
    }
  }
  

  问题，

  1>函数fillNextSeq有什么用？2> 为什么检查“items.get(i-1).isBefore(item)”而不是将当前项目与序列中的最新项目进行比较？

假设排序列表为(1, 5), (2, 1), (2, 2)，根据fillNextSeq函数，

第一个 (1, 5) 将被插入序列。那么item (2, 1) 不会被插入序列 b/c weight (2,1) is smaller than (1, 5).接下来，由于 (2, 1) 在 (2, 2) 之前，因此 (2, 2) 将被插入序列。

现在，序列包含 (1, 5) 和 (2, 2)，这是不正确的，因为 (1, 5) 的权重大于 (2, 2) 的权重。

谢谢

Answer 1

fillNextSeq 的用途是获取组中下一个增加高度/体重的序列。它通过将连续的项目添加到 ArrayList seq 来实现这一点，直到它遇到一个更重或更高的人。

items.get(i-1).isBefore(item) 的作用是检查下一个人是否比当前的人更矮更轻。请记住，您已经按高度和体重对人进行了排序，因此如果下一个人比​​当前人更高或更重，那么他们将在排序数组中排在当前人之前。所以有问题的行是将当前项目与序列中的最新项目进行比较，它只是通过比较它们在排序数组中的位置来完成。

希望这对您有所帮助，祝您好运!