Optimization Problem - Dynamic Programming

[Fl0W3R]

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.

 

[osilmag]

Hi. Welcome to the forums. Wouldn't you just conduct a greater than or less than test for the distances and assign/ask descending values as the distance increases?

 

[willem2]

What I did was, to make a sorted list of ALL the gift limits (without duplicates). All the gift limits have to be considered as minimum gift limit at the lowest distance.
For the smallest distance, you choose a gift limit from this list. This will be the minimum gift for distance 1. distance 1 friends with a lower limit, won't give any money. friends with a higher gift limit will be asked for more.

The minimum gift for distance 1 will be the maximum gift for distance 2. The search routine will call itself with for each value in the list of all the gift limits. This list will be made smaller when recursing, because of the maximum gift limit, which can only go down with distance.