在这样的塔中寻找尽可能多的人

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)"而不是将当前项目与seq中的最新项目进行比较？

假设排序列表是(1,5),(2,1),(2,2),基于fillNextSeq的功能,

第一个(1,5)将被推入序列中.然后项目(2,1)将不被推入序列b/c(2,1)的权重小于(1,5).接下来,由于(2,1)在(2,2)之前,因此(2,2)将被推入序列中.

现在,序列包含(1,5)和(2,2)不正确b/c(1,5)的权重大于(2,2)的权重.

谢谢

Answer 1

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

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

希望这有帮助，祝你好运！