Yes, this is a homework. I have been trying for hours and still blocked on same ideas, so I just asking someone to give me a little hint to the right direction and the rest is up to me, I am not looking for a complete solution. That said the problem is the following.

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.

My problem came up with the last bold sentence. If it was the case that simply you cannot ask someone an amount greater than what he/she claimed then it exists a very simple greedy method to solve this, but since it can happen the last sentence, in some cases can be convenient to ask your relative friend an amount greater than what they claims, and get zero from them in order to get a very high gift from a very generous far fried ( to get such amount you have to ask him for it and for hierarchy you have to ask at least the same amount to all the friend above him in hierarchy and this lead to getting zero from them).

I guess the way is dynamic programming, that is because the problem seems to have:

1. Overlapping substructures : different friendships distances, call these "layers" influence each other, in fact the minimum asking amount of a layer sets an upper_bound on deeper layers.
2. Optimal substructures : If I find the optimal total sum to the problem with j layers, this can be used to build the solution with j 1 layers, in fact I should choose if it worths to choose for upper_bounded amounts of layer j 1 or if it is the case to "sacrifice" some friend help from the layers 1...j asking them for more than their claims, in order to get revenue from a friend in layer j 1.

Thank you

CodePudding user response：

Hint. Go from the outside in.

At the very outermost layer, build a dictionary of the most you can ask, and how much you got. (This is a finite dictionary because there is no point in asking for an amount that is different than what someone is willing to give.)

As you go in, if you asked for G(k 1) of someone at the k 1 layer, and your biggest request at the kth layer is G(k), how much you make is how much you make from the outer layers with the biggest request having been G(k), plus nothing from anyone in the kth layer who is only willing to give less than G(k 1), plus all they are willing to give for those who are willing to give anywhere from G(k 1) to G(k) (note that G(k) must be bigger than or equal to G(k 1) due to your rules), plus G(k) from anyone who would have been willing to get more.

Keep track of how much you can make, and which jump was on the path that made that money.

By the time you get to the inner circle, you can just find the max, then walk the path out to get the solution that lead to that max.

CodePudding user response：

Here is the outline of a forward-DP approach that should work:

1. Make a list(V[]) of all of the offered values m_r, sorted from lowest to highest.

2. Make a list of all of your friends (D[]) sorted from farthest to closest. In the event of a tie, put those with lower m_r before those with higher m_r. We will use D[x].m to represent the value offered by your friend in D[x].

3. Make an n x n array(A[]) where the rows A[x,*] correspond to your sorted friends list D[x], and the columns A[*,y] corresponds to your sorted values V[y].

4. Fill in the first row (x=0, y=(0 to n-1)) using:

   A[0,y] = {if V[y] <= D[0].m Then V[y] Else 0}

5. Fill in the next row using the following formula:

   A[x,y] = {if V[y] <= D[x].m Then V[y] Else 0} MAX(A[x-1,j] for j=0 to y)

The maximum value of you can get then is the maximum value in the last row. The value to ask each friend can be determined from which j value is selected for each row by the MAX(..) function in step 5.

This will execute in O(n^3). There is a clever way to pre-calculate and save MAX(A[x-1,j] for j=0 to y) values for each A[x-1,y] that reduces it to O(n^2).