Сбор яблок с дерева

Question

У меня следующая проблема: мне дают дерево с N яблоками, для каждого яблока мне дают его вес и рост. Я могу собирать яблоки до заданной высоты H, каждый раз, когда я собираю яблоко, высота каждого яблока увеличивается с помощью U. Я должен выяснить максимальный вес яблок, которые я могу собрать.

1 ≤ N ≤ 100000
0 <{H, U, вес и рост яблок, максимальный вес} <2 <sup>31

Пример:

N=4  H=100  U=10  

height weight  
  82     30
  91     10
  93      5
  94     15

Ответ 45: сначала возьмите яблоко весом 15, а затем - весом 30.

Может ли кто-нибудь помочь мне решить эту проблему?

Answer 1

Работа в обратном направлении. Начните с выбора последнего яблока, которое вы выберете, затем второго до последнего и т. Д.

import heapq

def solve(apples, H, U):
  """Solve apple-picking problem.

  apples must be a sequence of (H, W) pairs.
  """
  if U == 0:
    return sum(x[1] for x in apples if x[0] <= H)

  apples = sorted(apples, reversed=True)
  # also creates a copy, to not modify caller's data

  picked_weight = 0
  available_weights = []  # stored negative for heapq

  offset = U - H % U
  if offset == U: offset = 0
  top = offset - U

  while (apples or available_weights) and top <= H:
    if available_weights:
      picked_weight += -heapq.heappop(available_weights)
      top += U
    else:
      top += U * max(1, (apples[-1][0] - top) // U)

    while apples and apples[0][0] <= top:
      heapq.heappush(available_weights, -apples.pop()[1])

  return picked_weight

Простой тест:

def test(expected, apples, H, U):
  actual = solve(apples, H, U)
  if expected != actual:
    print "expected=%r actual=%r | H=%r U=%r apples=%r" % (
              expected,   actual,     H,   U,   apples)

test(45, [(82, 30), (91, 10), (93,  5), (94, 15)], 100, 10)
test(22, [( 1,  1), ( 2,  1), (81, 10), (82, 10)], 100, 10)
test(20, [( 1, 10), ( 2, 10), (11,  1)], 20, 10)
test(20, [(81, 10), (82, 10), (90,  5)], 100, 10)
test(1, [(2**31 - 1, 1)], 2**31 - 1, 1)

---

Кто-то запросил C ++, так что вот оно. Этот код и логика почти идентичны приведенному выше Python, за исключением одного изменения: функции кучи в C ++ stdlib работают с максимальным значением вместо минимального, поэтому нет нужды в отрицании. (Я держал это автономно, но такие утилиты, как адаптер кучи и контейнерная вставка облегчат использование кода.)

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>


struct Apple {
  int h, w;

  friend bool operator<(Apple const& a, Apple const& b) {
    return a.h < b.h or (a.h == b.h and a.w < b.w);
  }
  friend bool operator>(Apple const& a, Apple const& b) {
    return b < a;
  }
  friend std::ostream& operator<<(std::ostream& s, Apple const& v) {
    s << '(' << v.h << ", " << v.w << ')';
    return s;
  }
};

template<class T, class C, T C::*M>
struct sum {
  T operator()(T const& cur, C const& next) { return cur + next.*M; }
};

int solve(std::vector<Apple> apples, int H, int U) {
  if (U == 0) {
    return std::accumulate(apples.begin(), apples.end(), 0, sum<int, Apple, &Apple::w>());
  }

  std::sort(apples.begin(), apples.end(), std::greater<Apple>());

  int picked_weight = 0;
  std::vector<int> available_weights;  // NOT stored negative, unlike Python code

  int offset = U - H % U;
  if (offset == U) offset = 0;
  int top = offset - U;

  while ((apples.size() or available_weights.size()) and top <= H) {
    if (available_weights.size()) {
      picked_weight += available_weights.front();
      std::pop_heap(available_weights.begin(), available_weights.end());
      available_weights.pop_back();
      top += U;
    }
    else {
      top += U * std::max(1, (apples.back().h - top) / U);
    }

    while (apples.size() and apples.back().h <= top) {
      available_weights.push_back(apples.back().w);
      std::push_heap(available_weights.begin(), available_weights.end());
      apples.pop_back();
    }
  }

  return picked_weight;
}

C ++ тесты:

template<int N>
void test(int expected, Apple (&apples)[N], int H, int U) {
  std::vector<Apple> v (apples, apples + N);
  int actual = solve(v, H, U);
  if (expected != actual) {
    std::printf("expected=%d actual=%d | H=%d U=%d apples=[",
                    expected,   actual,     H,   U);
    std::vector<Apple>::const_iterator i = v.begin();
    if (i != v.end()) {
      std::cout << *i;
      for (++i; i != v.end(); ++i) {
        std::cout << ", " << *i;
      }
    }
    std::cout << "]" << std::endl;
  }
}

int main() {
  {
    Apple data[] = {{82, 30}, {91, 10}, {93,  5}, {94, 15}};
    test(45, data, 100, 10);
  }
  {
    Apple data[] = {{ 1,  1}, { 2,  1}, {81, 10}, {82, 10}};
    test(22, data, 100, 10);
  }
  {
    Apple data[] = {{ 1, 10}, { 2, 10}, {11,  1}};
    test(20, data, 20, 10);
  }
  {
    Apple data[] = {{81, 10}, {82, 10}, {90,  5}};
    test(20, data, 100, 10);
  }
  {
    int n = 2147483647; // 2**31 - 1
    Apple data[] = {{n, 1}};
    test(1, data, n, 1);
  }
}

Answer 2

Первое, что нужно понять с этой проблемой, это то, что вы всегда должны собирать яблоки в порядке уменьшения высоты. Если вы собираетесь собирать яблоки A и B, где A выше, чем B, то нет смысла выбирать B первым, потому что это может подтолкнуть A слишком высоко; с другой стороны, выбор A сначала увеличит B, но не до высоты, превышающей A + U. Конечный результат одинаков в обоих случаях, но выбор B первым может исключить вероятность выбора A.

Первое, что нужно сделать, - это отсортировать яблоки в порядке убывания (т. Е. От самого высокого до самого низкого).

Затем разработайте рекурсивное решение проблемы (не обращая внимания на сложность). Глядя на первое яблоко, вы должны решить, "лучше ли его взять или оставить?" Таким образом, решение по существу:

макс ( возьмите первое яблоко , не берите первое яблоко ).

Вы можете записать это для второго яблока, третьего яблока и т. Д.

Это должно дать вам функцию с параметрами количество увиденных яблок и количество взятых яблок . Это дает вам размер пространства ввода функции O ( N ² ). Оттуда просто запомните ваши входные данные, и у вас есть алгоритм, который также имеет временную сложность O ( N ² ).

Answer 3

Вот большой намек:

Заказ яблок по уменьшению высоты.

Рассмотрим случай, когда все N яблок имеют разную высоту. Это тривиально, а затем просто собирайте яблоки один за другим по убыванию высоты, получая оптимальное решение (спросите себя, почему.)

Единственная трудность в этой проблеме возникает, если два или более яблок находятся на одной высоте. Фактически, единственная реальная трудность возникает, когда у вас есть разрыв между последовательными высотами яблока. Например, предположим, что у вас есть t временных шагов, прежде чем яблоки начнут выходить за пределы досягаемости. Это означает, что в этот момент вы можете рассматривать все яблоки в пределах t шагов самой высокой группы с равным приоритетом. Это потому, что у вас есть t «халява», прежде чем дерево начнет сопротивляться.

Вот картинка

  ------------- H
  _
  |
  [t]
  |
  _
  A A A A ... A <-closest group to H
  ._
  .|
  .[t]      all apples in this range should be treated with same priority
  .|        
  ._     

Answer 4

1) Определите для каждого яблока n, какова его продолжительность жизни, т.е. количество пиков, Pn, оно останется на дереве.

2) Из яблок с самым большим Pn выберите самые тяжелые. Уменьшите Pn для каждого оставшегося яблока в этой группе.

3) Повторите шаг 2, пока все яблоки не будут иметь Pn = 0.

Answer 5

Хорошо, вы знаете свою максимальную высоту и знаете, как далеко все будет двигаться вверх, когда вы что-то снимаете с дерева. В основном все между вершиной и вершиной - U будет недоступно после того, как вы уберете одно яблоко с дерева, так что, возможно, ваш первый выбор должен быть из этого набора?

edit: По мере продвижения по дереву, в каждом слоте берите самый тяжелый, а затем сравнивайте других кандидатов с теми, кого вы уже выбрали; если они тяжелее, чем вы выбрали, поменяйте местами.

(Да, это было бы проще снизу вверх, теперь, когда эта идея была выдвинута.)

Answer 6

Мне кажется, что для этого вам не нужно решение для динамического программирования, а просто жадный алгоритм. Сортируя яблоки по высоте, выберите самое тяжелое яблоко из яблок, высота которых составляет от 100 до 100 U. Затем удалите все эти яблоки до 100 U и повторите для 90 U (или увеличьте вес всех яблок на U). .

Поскольку вы всегда можете собрать яблоки дальше, идея состоит в том, чтобы выбрать самые тяжелые яблоки, которые в первую очередь упали бы.

Это должно работать, потому что увеличение высоты U постоянно. Там, где оно не является константой, вам придется использовать рекурсивную формулу в сочетании с запоминанием, которое является динамическим программированием.