Dynamic programming is a mathematical optimization/programming approach applicable if an optimal solution can be constructed efficiently from optimal solutions of its subproblems. A classic example is the Towers of Hanoi.
Questions tagged [dynamic-programming]
609 questions
4
votes
0 answers
A Dynamic Programming Question
$\underline{\text{Household Sector:}}$ The household comprises of a single agent whose objective function is to maximize the expected value of his lifetime utility which is a function of consumption of domestically produced goods and imported…
George
- 83
4
votes
1 answer
Dynamic Programming Algorithm Requirements
To my knowledge, a problem can be solved using Dynamic Programming if it has the following two properties:
Overlapping Subproblems
Optimal Substructure (an optimal solution can be constructed efficiently from optimal solutions of its…
Ogen
- 2,255
- 8
- 31
- 44
2
votes
0 answers
Dynamic programming and Lagrange multipliers
The problem is to solve dynamic programming problem
$$\sum_{t=1}^T\left(\frac{t^3}{3}+\frac{t^2}{2}\right)a_t^2 \to \max$$
where $\sum_{t=1}^T a_t =c$, and $a_t$ is assumed to be $\geq 0$.
It is expected to introduce $w_t = \sum_{i=1}^ta_i$ to solve…
Ruslan
- 21
2
votes
1 answer
Fake coin with weighing function
I have the following question:
"There are n coins, all weight equally except one.
In addition, we have a scale that can compare any s coins, for any s, with other s coins in the cost of w(s). The weighting informs us which sides is heavier or if…
M.Malone
- 21
- 3
2
votes
0 answers
Dynamic programming in macroeconomics
I try to solve the following maximization problem of a representative household with dynamic programming. However, my last result is not similar to the solution. Could any one help me?
$$\max\limits_{C_{t},H_t,N_t} E_0 \sum_{t=0}^{\infty}…
DB225681
- 57
1
vote
1 answer
How to convert mathematical programming problem to dynamic programming problem
Do not know how to approach this problem. The task is to convert the problem of mathematical programming:
$\max(\prod_{i=1}^nx_i)$
$\sum_{i=1}^na_ix_i\leq c$
$c \gt 0, a_i \gt 0$
into a problem of dynamic programming. Write down Bellman equations…
Jacobian
- 113
1
vote
1 answer
Cost of conversion of string $A$ to string $B$
We are given $2$ strings $A=[1 \dots m]$ and $B[1 \dots n]$ and the following $3$ operations are allowed:
Insert a charachter,with cost $c_i$
Delete a character,with cost $c_d$
Replace a character,with cost $c_r$
We are looking for the optimal…
evinda
- 7,823
1
vote
2 answers
Longest Common Subsequence
Let $X=$ and $Y=$ be sequences and let $Z=$ a longest common subsequence (LCS) of $X$ and $Y$.Then:
If $x_m=y_n$,then $z_k=x_m=y_n$ and $Z_{k-1}$ is a LCS of $X_{m-1}$ and $Y_{n-1}$
If $x_m \neq y_n$ and…
evinda
- 7,823
1
vote
0 answers
Dynamic Programming Question
A train is given to two children as a gift. A train consists of a sequence of cars connected in a single line. There is an even number of cars, and the two children wish to divide them up. They do this by taking one car at a time from one end of the…
Dave Newbury
- 11
1
vote
0 answers
What is a Viterbi algorithm that exploits sparseness of transition matrix?
What is a Viterbi algorithm that exploits sparseness of transition matrix?
In
PYIN: A FUNDAMENTAL FREQUENCY ESTIMATOR
USING PROBABILISTIC THRESHOLD DISTRIBUTIONS
Matthias Mauch and Simon…
mavavilj
- 7,270
1
vote
0 answers
What the meaning of "impatience" in Bellman equation?
From wiki:
A dynamic decision problem
... Finally, we assume impatience, represented by a discount factor $0 < \beta < 1$
What the meaning of "impatience"? I can't understand even if I read https://en.wiktionary.org/wiki/impatience.
huang
- 111
1
vote
0 answers
Convergence of value iteration of dynamic programming
$\newcommand{\R}{\mathbb{R}}\newcommand{\T}{\mathbb{T}}$Let $\ell:\R^n\times\R^m\to[0, \infty)$ be a continuous stage cost function and $f:\R^n\times\R^m\to\R^n$ be a continuous function associated with the system
$$
x_{t+1} = f(x_t, u_t).
$$
Let…
John McSimon
- 123
- 5
1
vote
0 answers
Solving dynamic program with open interval $\max_{\{u_t\}{T-1\\ t=0}} \ \ \sum_{t = 0}^{T-1}-(x_t^2-(x_t+u_t)^2)^2-x_T^4$
I want to solve this dynamic program but I am quite unsure about the approach, as there is an open interval for the control space.
I would appreciate any suggestions.
$$\max_{\{u_t\}^{T-1}_{t=0}} \ \ \sum_{t =…
Silas93
- 11
1
vote
0 answers
Proving Threshold Properties of a Dynamic Programming Problem
I'm struggling with the following simple dynamic programming problem for a couple of days. This is my first time to try to solve a dynamic programming problem analytically. The structural property is so intuitive, yet I find no way to prove it. The…
KevinKim
- 209
1
vote
0 answers
How to combine sites with some limitation?
I have a dataset from a real clinical trial. This is the virtual sample:
SiteID Control Placebo Rate
1 30 8 3.8
3 9 4 2.3
4 27 9 3
5 23 3 7.7
6 3 1 3
7 23 7 3.3
8 13 6 2.2
9 19 1 19
10 5
11 23 15 …
whymath
- 121
- 2