Найти как можно больше людей в такой башне

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), (75190).

• Шаг 2. Найдите самую длинную последовательность который содержит увеличение высоты и увеличение веса. Для этого мы:

• а) Начало в начале
  последовательность. В настоящее время max_sequence пустой.

• b) Если для следующего элемента,
  рост и вес не больше чем у предыдущего пункта, мы
  пометить этот товар как «непригодный»

  в) Если В найденной последовательности больше элементов, чем «Макс. Последовательность» становится «Макс. последовательность".

• 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,

first (1, 5) будет вставлен в последовательность. Тогда пункт (2, 1) не будет вставлен в последовательность, б / с вес (2,1) меньше, чем (1, 5). Далее, поскольку (2, 1) раньше, чем (2, 2), поэтому (2, 2) будут вставлены в последовательность.

Теперь последовательность содержит (1, 5) и (2, 2), что неверно, т.к. вес (1, 5) больше, чем (2, 2).

Спасибо

Answer 1

Использование fillNextSeq - выборка следующей последовательности увеличения роста / веса в вашей группе. Это достигается путем добавления последовательных элементов в последовательность ArrayList до тех пор, пока не встретится с более тяжелым или высоким человеком.

Функция items.get(i-1).isBefore(item) заключается в проверке, является ли следующий человек короче и легче текущего. Помните, что вы уже отсортировали своих людей по росту и весу, поэтому, если следующий человек в последовательности будет выше или тяжелее текущего человека, он будет находиться перед текущим человеком в отсортированном массиве. Таким образом, рассматриваемая строка сравнивает текущий элемент с последним в последовательности, она просто делает это путем сравнения их позиций в отсортированном массиве.

Надеюсь, это поможет, удачи!

Answer 2

Я написал решение в c #, которое состоит из двух частей.

Часть 1: создание компаратора, который сортирует по росту и весу (рост и вес) в порядке возрастания.

Часть 2: - линейный поиск по отсортированному массиву с конца, так что a [i] должно быть меньше, чем [i-1] по росту и весу.

ниже код. У меня есть несколько тестовых случаев и я проверил, что код работает нормально. но кое-что, как я чувствую, в этом решении скрыта ошибка. Запросите экспертов для подтверждения кода.

Класс My Person, который реализует IComparer

public class Person : IComparer<Person>
{

    public double Height { get; set; }
    public double Weight { get; set; }

    public int Compare(Person p1, Person p2)
    {

        if ((p1.Height > p2.Height) && (p1.Weight > p2.Weight))
            return 1;

        return -1;
    }

}

Мой основной метод

public int NumberOfPeople(Person[] p)
    {

        if (p == null || p.Length == 0)
            return -1;

        Array.Sort(p, new Person());
        int last = p.Length - 1;
        int count = 1;
        for (int i = p.Length - 2; i >= 0 ; i--)
        {
            if ((p[i].Height < p[last].Height) && p[i].Weight < p[last].Weight)
            {
                last = i;
                count++;
            }
        }
        return count;
    }

любая помощь будет признательна.

Answer 3

Я думаю, что мы можем использовать динамическое программирование, чтобы решить эту проблему.Вот моя идея:

L(j) -- the largest possible people ending at j ( 0 < j < n)
L(j) = max { L(i) } + 1 where i<j && ht(i)< ht(j) && wt(i)< wt(j)
we're looking for max{L(j)} where 0<j<n.

Для каждого j мы храним список массивов.Хт и вес людей в списке массивов увеличивается.Имея дело с j-м человеком, мы выполняем бинарный поиск в списке массивов всех

List<HtWt> F( HtWt[] in, int n){

   ArrayList<HtWt> out = new ArrayList<HtWt>(n);
   out[0].add(int[0]); 

   int maxl = 0, tj = 0;

   for(int j = 1; j < n; j++){

      // choose the longest among all available
      int jl = 0, ti = 0, tp = 0;

      for( i = 0; i < j; i++){

         // find the first greater element in out[i]
         int x = F(out[i], in[j]);

         // find an appropriate position in i to insert j
         if ( x != -1)  
         {
            // compare with the longest list found so far
            if( (out[i].size + 1) > jl ){
              jl = (out[i].size + 1);
              ti = i;
              tp = x;
          }// if             
      }// for i
     out[j] = out[i];
     out[j].add( tp, o[j]);

     if ( out[j].size > maxl){
       maxl = out[j].size
       tj = j;
     } // if
   } // for j

   return out[tj];
 }  // F

 running time: n + nlogn

 For example, (80, 10), (80, 80), (90, 10), (90, 20), (90, 30)
 j = 0, len = 1, out[0] = (80,10) 
 j = 1, len = 1, out[1] = (80,80)
 j = 2, len = 1 , out[2] = (90, 10)
 j = 3, len = 2, out[3] = (80,10)->(90,20)
 j = 4, len = 1, out[4] = (90, 30)