- #1

Fl0W3R

- 1

- 0

Thread moved from the technical forums to the schoolwork forums

**Summary::**Hi, this is an exercise from an algorithm course. I have been trying for hours but I have no successful ideas on how to solve it. I can only understand that DP is the correct approach, since Greedy method does not work.

Suppose you have *n* friends that wants to give you an amount of money to help you buy a new smartphone. Each of them claims a value m_r that represent the max amount the friend *r* is willing to give you. The level of friendship you have with your friends can be classified as follow:

Your closer friends are at a distance of 1 from you.

Then there are friends at a distance of 2 from you, and so on, until the friend at distance *k* that are ones with you have a less strong friendship.

You have to tell each of your friend an amount *g_r* that represent what you would like to receive from him/her. In order to be coherent with the friendship hierarchy you want to satisfy the following constraint:

Let say the friendship is measured in distance by the function *f(r)* one of your closest friend *r_1* is at a distance *f(r_1) = 1* and for another at distance 3, *r_2*, it is *f(r_2) = 3*, then you must not ask *r_3* an amount *g_3* > *g_1*.

In general for each pair of friends *r_i* and *r_j* if is the case that *f(r_i) < f(r_j)* then must also be *g_i >= g_j*. **For each friend *r* you can ask an amount *g_r > m_r* but in that case that friend will give you 0.** The goal is to calculate the amount to ask for each friend in order to maximaze the total amount received.

So at every distance, call layer there is an upperbound on how much you can ask someone, and that is the minimum request you did in the above layer. The reason why greedy method does not work is that could be the case the optimum total value is reached asking some one from layer 1 to k an amount greater than how much they are willing to give, getting 0 from that, but augmenting the upperbound so that you can ask a friend in layer k + 1 for a great amount ( if he/she can give you)

An example:

Layer 1 : 2000, 300, 300

Layer 2 : 2200, 400

The best optimum is reached if we ask every one at the first layer for 2000, and on the second layer 2000 and 400.