Найдите максимально возможное количество людей в такой башне
Во-первых, давайте посмотрим на вопрос,
Цирк проектирует башенную рутину, состоящую из людей, стоящих поверх друг друга
плечи. По практическим и эстетическим причинам каждый человек должен быть как короче, так и легче, чем человек ниже него или нее. Учитывая высоты и веса каждого человека в цирке, напишите способ вычисления максимально возможного числа людей
в такой башне.
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. Найдите самую длинную последовательность
который содержит увеличение высоты и
увеличивая вес. Для этого мы:
-
a) Начните с начала
последовательность. В настоящее время max_sequence
пустой.
-
b) Если для следующего элемента,
высота и вес не больше
чем в предыдущем пункте, мы
отметьте этот элемент как "непригодный"
c) Если
найденная последовательность содержит больше предметов, чем
"max sequence", он становится "max
последовательность ".
-
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).
Спасибо
Ответы
Ответ 1
Использование fillNextSeq - это выбор следующей последовательности увеличения высоты/веса в вашей группе. Он делает это, добавляя последовательные элементы в ArrayList seq, пока не встретится с более тяжелым или более высоким человеком.
Функция items.get(i-1).isBefore(item)
заключается в проверке того, является ли следующий человек короче и светлее текущего. Помните, что вы уже отсортировали своих людей по высоте и весу, поэтому, если следующий человек в последовательности будет выше или тяжелее текущего человека, тогда они будут находиться перед текущим человеком в отсортированном массиве. Таким образом, рассматриваемая строка сравнивает текущий элемент с последним в последовательности, он просто делает это, сравнивая свои позиции в отсортированном массиве.
Надеюсь, это поможет, удачи!
Ответ 2
Я думаю, что мы можем использовать динамическое программирование для решения этой проблемы. Вот моя идея:
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 мы сохраняем список массивов. Увеличиваются ht и wt лиц в списке массивов. Когда мы имеем дело с 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)
Ответ 3
Я написал решение в С#, которое состоит из двух частей.
Часть 1: - создать сравнитель, который сортируется по высоте и весу (высота и вес) в порядке возрастания.
Часть 2: - линейный поиск по сортированному массиву с конца так, что a [i] должен быть меньше, чем [i-1] как по высоте, так и по весу.
ниже - это код. У меня есть некоторые некоторые unit test случаи и проверили, что код работает нормально. но некоторые, как я чувствую, что в этом решении есть ошибка. Запросите экспертов здесь, чтобы проверить код.
Класс 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;
}
любая помощь будет оценена.