Picking apples from a tree

Question

I have the following problem: I am given a tree with N apples, for each apple they give me weight and height. I can select apples up to a certain height H, each time I select an apple, the height of each apple increases with U. I have to find out the maximum weight of apples that I can choose.

1 ≤ N ≤ 100000
0 <{H, U, weight and height of apples, maximum weight} <2 ³¹

Example:

N=4 H=100 U=10 height weight 82 30 91 10 93 5 94 15 

Answer: 45: First select an apple weighing 15, then weighing 30.

Can someone help me approach this issue?

Answer 1

Work back. Start by choosing the last apple you choose, then the second to the 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 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 

A 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. This is almost identical code and logic for the aforementioned Python, with one exception: C ++ stdlib heap functions work with the maximum value instead of min, so there is no need for negation. (I kept this standalone, but utilities like a heap adapter and an insert container will make the code more usable.)

 #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 ah < bh or (ah == bh and aw < bw); } friend bool operator>(Apple const& a, Apple const& b) { return b < a; } friend std::ostream& operator<<(std::ostream& s, Apple const& v) { s << '(' << vh << ", " << vw << ')'; return s; } }; template<class T, class C, TC::*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); } } 

Answer 2

The first thing to understand with this problem is that you should always choose apples in descending order of height. If you are going to choose apples A and B, with A above B, then there is no choice of point B in the first place, because this may push A too high; on the other hand, the choice of A would first increase B, but not to a height greater than A + U. The end result is the same in both cases, but the choice of B may first exclude the possibility of choosing A.

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

Then create a recursive solution to the problem (ignoring complexity). Looking at the first apple, you need to decide: "Is it better to take it or leave it?" Thus, the solution is essentially:

max (take the first apple, do not take the first apple).

You can repeat this for the second apple, third apple, etc.

This should give you a function with parameters for the number of visible apples and the number of accepted apples . This gives you the size of the input space of the O (N ² ) function. From there, just memorize your inputs, and you have an algorithm with O (N ² ) time complexity.

Answer 3

Well, you know your maximum height, and you know how far everything will go up when you pick something from the tree. Basically, everything is between the top and the top - U will not be available after you pick one apple from the tree, so maybe your first choice should be from this set?

edit:. When you go through the tree, in each slot you take the hardest, and then check other candidates against those that you have already chosen; if they are heavier than what you chose, replace.

(Yes, that would be easier from the bottom up, now that this idea has been put forward.)

Answer 4

1) Define for each apple, n, how long its life - that is. the number of peaks, Pn, it will remain on the tree.

2) From the apples with the highest Pn, select the heaviest. Decrement Pn for each remaining apple in this group.

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

Answer 5

Here is a great hint:

Order apples by reducing height.

Consider the case when all N apples have different heights. This is trivial, and then just pick apples one by one with decreasing height, which gives 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 time steps t before apples begin to go out of reach. This means that at this point you can process all the apples in steps t the highest group with equal priority. This is because you have t "freebie" before the tree begins to fight back.

Here is the image

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

Answer 6

It seems to me that for this you do not need a solution for dynamic programming, but just a greedy algorithm. Sorting apples by height, select the heaviest apple from apples with a height of 100 to 100 - U. Then remove all these apples to 100 - U and repeat for 90 - U (or increase the weight of all apples U).

Because you can always pick apples farther, the idea is to pick the heaviest apples that will first fall out of reach.

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