Picking apples off a tree_问答_开发者_运维开发者技术经验分享

I have the following problem: I am given a tree with N apples, for each apple I am given it's weight and height. I can pick apples up to a given height H, each time I pick an apple the height of every apple is increased with U. I have to find out the maximum weight of apples I can pick.

1 ≤ N ≤ 100000

0 < {H, U, apples' weight and height, maximum weight} < 2³¹

Example:

N=4  H=100  U=10  

height weight  
  82     30
  91     10
  93      5
  94     15

The answer is 45: first pick the apple with the weight of 15开发者_运维技巧 then the one with the weight of 30.

Could someone help me approach this problem?

Work backwards. Start by deciding the last apple you will pick, then the second to last, etc.

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

Simple test:

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)

Someone requested C++, so here it is. It's nearly identical code and logic to the above Python, except for one change: C++ stdlib's heap functions work with the max value instead of the min, so no need for the negation. (I kept this self-contained, but utilities such as a heap adapter and container inserter will make the code easier to use.)

#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++ tests:

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);
  }
}

The first thing to realize with this problem is that you should always pick apples in order of decreasing height. If you are going to pick apples A and B, with A higher than B, then there is no point picking B first because it may push A too high; on the other hand, picking A first would increase B, but not to a height greater than A+U. The end result is the same in both cases, but picking B first may eliminate the chance of picking A.

The first thing to do is to sort the apples in decreasing order (i.e. from highest to lowest).

Next, devise a recursive solution to the problem (ignoring complexity). Looking at the first apple, you have to decide "would it be better to take it, or leave it?" So the solution is essentially:

max(take first apple, don't take first apple).

You can recurse this down for the second apple, third apple etc.

This should give you function with parameters number of seen apples and number of taken apples. This gives you a function input space size of O(N²). From there, just memoize your inputs and you have an algorithm that has time complexity of O(N²) as well.

1) Determine for each apple, n, how long its life is--i.e. the number of picks, Pn, it will remain on the tree.

2) From the apples with the largest Pn, pick out the heaviest. Decrement Pn for each remaining apple in this group.

3) Repeat step 2 until All apples have Pn = 0.

Here is a big hint:

Order the apples by decreasing height.

Consider the case where all N apples are a different heights. This is trivial, then just pick the apples one by one in decreasing height yielding the optimal solution (ask yourself why.)

The only difficulty in this problem arises if two or more apples are at the same height. In fact, the only real difficulty arises when you have a gap between consecutive apple heights. For example, suppose you have t time steps before apples start going out of reach. That means that at this exact moment you can treat all apples within t steps of the highest group with equal priority. This is because you have t "freebie" picks before the tree starts fighting back.

Here's a picture

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

Ok, you know your maximum height, and you know how far everything will move up when you pick something off of the tree. Basically everything between the top and top - U will be unavailable after you pick one apple off of the tree, so maybe your first pick should be from that set?

edit: As you march down the tree, at each slot take the heaviest and then check the other candidates against the ones you've already selected; if any are heavier than one you've picked, swap in.

(Yes, this would be easier bottom-up, now that that idea has been put forth.)

It seems to me that you don't need a dynamic programming solution for this, but just a greedy algorithm. Sorting the apples by height, pick the heaviest apple from the apples whose height is between 100 and 100 - U. Then remove all those apples up to 100 - U and repeat for 90 - U (or increase the weight of all apples by U).

Because you can always pick the apples further down, the idea is to pick the heaviest apples which would fall out of reach first.

This should work because the increase in height U is constant. Where it not constant, then you'd have to use a recursive formula in combination with memoization, which is dynamic programming.