在这样的塔中找到尽可能多的人 [英] Find the largest possible number of people in such a tower

问题描述

首先，让我们看一个问题，

First, let's see the question,

马戏团正在设计一个铁塔程序，由站在另一个
肩膀上的人组成。出于实用和审美的原因，每个人都必须比其下方的人矮一些和矮一些。给定马戏团中每个人的身高和体重，编写一种方法来计算此类塔中最大人数的人
。

A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

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)

但我不太了解以下解决方案：

But I don't quite understand the solution as follows:

书中建议的解决方案：

• 步骤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。找到最长的序列
  ，其中包含增加的高度和
  的权重。为此，我们：

• Step 1. Sort all items by height first, and then by weight. This means that if all the heights are unique, then the items will be sorted by their height. If heights are the same, items will be sorted by their weight. Example: »»Before sorting: (60, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68,110). »After sorting: (56, 90), (60, 95), (60,100), (68, 110), (70,150), (75,190).

• Step 2. Find the longest sequence which contains increasing heights and increasing weights. To do this, we:

a）从

序列的开头开始。当前，max_sequence为
空。

a) Start at the beginning of the
sequence. Currently, max_sequence is empty.

b）如果对于下一项，

的高度和重量为不超过上一个项目的
，我们

将该项目标记为不适合

b) If, for the next item, the
height and the weight is not greater than those of the previous item, we
mark this item as "unfit"

c）如果$ b $找到的b序列比
最大序列具有更多的项目，则变为最大
序列。

c) If the sequence found has more items than "max sequence", it becomes "max sequence".

d）之后，从不合适项目开始重复搜索
，

直到搜索结束

d) After that the search is repeated from the "unfit item",
until we reach the end of the
original sequence.

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> what is the usage of the function fillNextSeq? 2> why check "items.get(i-1).isBefore(item)" rather than compare the current item with the latest one in the seq?

假设基于fillNextSeq函数的排序列表为（1、5），（2、1），（2、2）

Assume the sorting list is (1, 5), (2, 1), (2, 2), based on the function of fillNextSeq,

first（1、5）将被推入序列。然后项目（2，1）将不会被推入序列（2,1）的b / c权重小于（1，5）。接下来，由于（2，1）在（2，2）之前，所以（2，2）将被推入序列。

first (1, 5) will be pushed into the sequence. Then item (2, 1) will not be pushed into the sequence b/c weight of (2,1) is smaller than (1, 5). Next, since (2, 1) is before (2, 2), so (2, 2) will be pushed into the sequence.

现在，该序列包含（ 1，5）和（2，2）不正确b / c（1，5）的权重大于（2，2）的权重。

Now, the sequence contains (1, 5) and (2, 2) which is not correct b/c the weight of (1, 5) is larger than that of (2, 2).

谢谢

推荐答案

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

The usage of fillNextSeq is to fetch the next sequence of increasing height/weight in your group. It does this by adding successive items to the ArrayList seq until it comes across a heavier or taller person.

items.get（i-1）.isBefore（item）的功能是检查下一个人比目前的人矮而轻。请记住，您已经按照身高和体重对您的人进行了排序，因此如果顺序中的下一个人比​​当前人高或重，那么他们将在排序数组中排在当前人之前。因此，有问题的那一行是比较当前商品与序列中的最新商品，它只是通过比较它们在已排序数组中的位置来完成的。

The function of items.get(i-1).isBefore(item) is to check if the next person is shorter and lighter than the current one. Remember that you have already sorted your people by height and weight, so if the next person in sequence is taller or heavier than the current person then they will come before the current person in the sorted array. So the line in question IS comparing the current item with the latest one in the sequence, it's just doing it by comparing their positions in the sorted array.

希望有帮助，祝您好运！

Hope this helps, good luck!

这篇关于在这样的塔中找到尽可能多的人的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！