Блог

Давайте сначала рассмотрим несколько примеров:

Если у вас 1 яйцо, сколько бросков вам нужно для здания в 2 этажа? 3 этажа? 4?
Очевидно, что это просто. Вам нужно 2, 3 и 4 броска соответственно, и, как правило, n бросков.

Что, если у вас есть 2 яйца? Сколько бросков для 2 этажей? 3? 4?
Очевидно, что 2 броска на 2 этажа… 3 все же интересно. Если кинуть яйцо со 2_{— й} этаж, и она не ломается, то бросьте ее с 3_й этаж и вы знаете ответ (он либо сломается на 3 —_й этаж, или не на всех). Если первая яйцеклетка разрывает на 2_{— й} пол бросаю, ты бросаешь другое яйцо из первого этажа и снова, ты знаешь ответ (она или распадается на 1_ст пол и это ответ или его нет, и ответ на 2_{— й} этаж). Ха… так только 2 броска по 3 этажи. Но это не работает на 4_-м этаже, и нам нужен еще один бросок. Этот дополнительный бросок может «купить нам» больше, чем просто один этаж. Это действительно приведет нас на 6_-й этаж (скоро мы увидим, как это работает).

Также оказывается, что наличие большего количества яиц не будет иметь никакого значения для 6-этажного здания или меньше.

Предположим, мы знаем, сколько этажей мы можем покрыть m-1 яйцами и n-1 бросками, давайте назовем это h. Если у нас есть m яиц и n бросков, нашей оптимальной стратегией было бы пропустить первое яйцо с h 1_-го этажа — это самый высокий этаж, на который мы можем пойти. Если яйцо разобьется, у нас будет достаточно яиц (m-1) и достаточное количество бросков (n-1), чтобы найти ответ на оставшихся h этажах. Наш следующий шаг, если яйцо не разобьется, — подняться на достаточное количество этажей, чтобы нас накрыло (m, n-1), и продолжать делать это, пока у нас не останется бросков. Таким образом, мы достигнем максимального покрытия при любой комбинации яиц и бросков.

Это объясняет нашу оптимальную стратегию, но мы не определили, сколько этажей будет (m, n) покрывать. Хотя это довольно просто: (m-1, n-1) покроет несколько h этажей, сам бросок (m, n) будет составлять h 1 этаж, а остальные броски позволят использовать дополнительные (m, n-1) этажи. К настоящему времени моделирование проблемы должно быть достаточно ясным, и мы можем определить простую рекурсивную функцию для вычисления максимальной высоты покрытия:

 function maxHeightByEggThrows(eggs, throws) {
  if(eggs === 0 || throws === 0)
    return 0;

  return maxHeightByEggThrows(eggs - 1, throws - 1)   1  
         maxHeightByEggThrows(eggs, throws - 1);
}
  

И это работает безупречно, но это плохая, неэффективная реализация. Давайте попробуем DP:

 function maxHeightByEggThrowsDP(eggs, throws) {
  let eggThrows = [[]];

  for(let i = 0; i < throws; i  ) {
    // A single egg can cover has many floors has throws are allowed
    eggThrows[0].push(i   1);
  }
  for(let i = 1; i < eggs; i  ) {
    // Any number of eggs can only cover 1 floor with a single throw
    eggThrows.push([1]);
  }

  for(let i = 1; i < throws; i  ) {
    for(let j = 1; j < eggs; j  ) {
      eggThrows[j][i] = eggThrows[j - 1][i - 1]   eggThrows[j][i - 1]   1;
    }
  }

  return eggThrows[eggs - 1][throws - 1];
}
  

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

 function maxHeightByEggThrowsDP(eggs, throws) {
  let eggThrows = [[]];

  for (let i = 0; i < throws; i  ) {
    // A single egg can cover has many floors has throws are allowed
    eggThrows[0].push(i   1);
  }
  for (let i = 1; i < eggs; i  ) {
    // Any number of eggs can only cover 1 floor with a single throw
    eggThrows.push([1]);
  }

  for (let i = 1; i < throws; i  ) {
    for (let j = 1; j < eggs; j  ) {
      eggThrows[j][i] = eggThrows[j - 1][i - 1]   eggThrows[j][i - 1]   1;
    }
  }

  return eggThrows;
}

const eggs = 10;
const throws = 15;
let eggThrows = maxHeightByEggThrowsDP(eggs, throws);


// display our data (boilerplate code)
// add a "row header" so we can read the egg count
eggThrows.forEach((row, i) => row.unshift(i   1));
d3.select('#eggThrows>tbody').selectAll('tr').data(eggThrows).enter().append('tr').selectAll('td').data(d => d).enter().append('td').text(t => t);

d3.select('#throwsHeader').attr('colSpan', throws);  

 #eggThrows > thead td {
  padding: 5px;
  background-color: #404040;
  color: white;
}

#eggThrows > tbody td {
  padding: 5px;
  background-color: #C0C0C0;
}
#eggThrows > tbody td:first-child {
  background-color: #C0FF30;
}  

 <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>
<table id="eggThrows"><thead><tr><td>Eggs</td><td id="throwsHeader">Throws</td></tr></thead><tbody></tbody></table>  

Итак, мы знаем максимальную высоту, но нам нужен первый этаж для броска… Оказывается, есть несколько вариантов. Например, теперь мы можем видеть, что в классическом случае «2 яйца 14 бросков» мы действительно можем получить ответ для 105 этажей, а не только для 100. Мы также знаем, что 2 яйца и 13 бросков покрывают 91 этаж, поэтому мы могли бы бросить первое яйцо с 9_-го этажа и все равно найти решение за 14 бросков.

И теперь мы можем ответить на вопрос:

Первый этаж, с которого нужно бросать, не выше (maxHeightByEggThrows(m-1, n-1) 1) и не ниже ([высота здания] — maxHeightByEggThrows(m, n-1))
(для 3 яиц и 100 этажей это между 8_-м и 37_-м этажами)

Эта проблема может быть решена с помощью следующих 3 подходов (которые я знаю) :

1. Динамическое программирование
2. Решение с использованием двоичного дерева поиска
3. Решение путем получения прямой математической формулы для максимального количества этажей, которые могут быть протестированы или покрыты заданным количеством яиц и заданным количеством капель

Позвольте мне сначала определить некоторые символы, которые используются в анализе, выполняемом впоследствии :

 e = number of eggs
f = number of floors in building
n = number of egg drops 
Fmax(e, n) = maximum number of floors that can be tested or covered with e eggs and n drops
  

Суть подхода динамического программирования заключается в следовании рекурсивной формуле для Fmax:

 Fmax(e, n) = 1   Fmax(e-1, n-1)   fmax(e, n-1)
  

И суть получения прямой математической формулы для Fmax заключается в следующей рекурсивной формуле для Fmax:

 Fmax(e, n) = { ∑Fmax(e-1,i) for i = 1 to n } - Fmax(e-1, n)   n 
  

Альтернативное решение с использованием бинарного дерева поиска (BST) также возможно для этой проблемы. Чтобы облегчить наш анализ, давайте нарисуем BST с небольшими изменениями следующим образом:

 1.    If egg breaks then child node is drawn on left down side
2.    If egg does not break then child node is drawn straight down side
  

Если мы рисуем BST с указанным выше видом представления, то ширина BST представляет количество яиц.

Любой BST с f числом узлов, нарисованный с использованием вышеуказанного представления и подверженный ширине ограничения BST <= e (количество яиц), является решением, но это может быть не оптимальное решение.

Следовательно, получение оптимального решения эквивалентно получению расположения узлов в BST с минимальной высотой, подверженной ограничению: ширина BST <= e

Более подробную информацию обо всех вышеупомянутых 3 подходах см. в моем блоге: 3 подхода к решению обобщенной проблемы удаления яиц

Вот алгоритм, который был реализован в swift (это включает в себя концепцию всех предыдущих алгоритмов):-

 //Here n is number of eggs and k is number of floors
func eggDrop(_ n: Int, _ k: Int) -> Int {
        var eggFloor: [[Int]] = Array(repeating:Array(repeating: 0, count: k 1),count: n 1)
        if k == 1 {
            return k
        }
        for i in 1...n {
            eggFloor[i][1] = 1
            eggFloor[i][0] = 0
        }
        for j in 1...k {
            eggFloor[1][j] = j
        }
        for i in 2...n {
            for j in 2...k {
                eggFloor[i][j] = Int(INT_MAX)
                for x in 1...j {
                    let attempts = 1   max(eggFloor[i-1][x-1], eggFloor[i][j-x])
                    if attempts < eggFloor[i][j] {
                        eggFloor[i][j] = attempts
                    }
                }
            }
        }
        return eggFloor[n][k]
    }