# Optimization Problem - Dynamic Programming

• Fl0W3R
In summary, you can choose a gift limit from a list of all the gift limits at the lowest distance, and it will be the minimum gift for distance 1.
Fl0W3R
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.

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?

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.

## What is an optimization problem in the context of dynamic programming?

An optimization problem in the context of dynamic programming is a problem that involves finding the best possible solution from a set of feasible solutions. This solution is often referred to as the "optimal" solution and is determined by minimizing or maximizing a specific objective function, while also satisfying a set of constraints.

## How does dynamic programming approach optimization problems?

Dynamic programming approaches optimization problems by breaking them down into smaller subproblems and solving them recursively. This allows for a more efficient and systematic way of finding the optimal solution compared to other traditional methods, such as brute force or greedy algorithms.

## What are the key components of a dynamic programming solution?

The key components of a dynamic programming solution are the optimal substructure and overlapping subproblems. Optimal substructure means that the optimal solution to a larger problem can be constructed from optimal solutions to its smaller subproblems. Overlapping subproblems refer to the fact that the same subproblems are often encountered multiple times in the process of finding the optimal solution.

## What are some common applications of dynamic programming?

Dynamic programming has a wide range of applications, including but not limited to: resource allocation, scheduling, knapsack problems, shortest path problems, and sequence alignment. It is also commonly used in fields such as economics, computer science, and operations research.

## What are some limitations of dynamic programming?

One limitation of dynamic programming is that it can only be applied to problems that exhibit optimal substructure and overlapping subproblems. Additionally, the time and space complexity of dynamic programming algorithms can be quite high, making it less suitable for solving very large problems. Finally, dynamic programming may not always provide the most efficient solution, as it can be outperformed by other specialized algorithms for certain types of problems.

• Programming and Computer Science
Replies
2
Views
1K
• General Math
Replies
6
Views
1K
• Programming and Computer Science
Replies
1
Views
2K
• Linear and Abstract Algebra
Replies
7
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus
Replies
6
Views
2K
• Special and General Relativity
Replies
40
Views
2K
• Aerospace Engineering
Replies
5
Views
7K
• Topology and Analysis
Replies
4
Views
2K
• Mechanics
Replies
4
Views
3K