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
0
votes
1 answer
In Blackwell's condition for T to be a contraction mapping, we require that satisfies discounting. What is the intuition of discounting?
The discounting condition is as follow:
There exists some $β∈(0,1)$ such that $[T(f+a)](x)≤(Tf)(x)+βa$, for all $f∈B(X),a≥0,x∈X$.
While the monotonicity condition makes sense, I can't give a nice meaning to this property.
Tecon
- 29
0
votes
1 answer
Maximizing #products with dynamic programming
Ok so we have lets say 2 big wooden stakes, each has a length of $2$ $meters$. Our goal is to create as many photo frames as possible.
Each photo frame is consisted of $2\times50cm$ pieces and $2\times30cm$ pieces.
I want to create a dynamic…
Mario Zelic
- 319
0
votes
2 answers
Coin change minimum lower bound
Ok so we have coins with values 1,2 and 3. I was told that the minimum number of coins we need to create number $x$ is this:
$\lfloor {x\over 3 }\rfloor+\lfloor {x\mod3\over 2 }\rfloor +((x\mod3)\mod 2)$
but i simply can't find a way to prove it. I…
Mario Zelic
- 319
0
votes
1 answer
Dynamic Programming - Bridge crossing
Assume that the edge labels are likelihood as percentage of a bridge collapsing when the crossing is attempted shown in the picture below.
Find the Probability of survival for each leg in the network and draw the
network with these probabilities…
Moe21
- 63
0
votes
0 answers
How can I modify Wagner Whitin algorithm to construct an algorithm where the decision is whether or not to order in a given period
i.e. among N time periods the no. of setups should not exceed any k.
By using dynamic forward equations
Our Wagner Whithin method is this:
Let
St setup cost in period t
Yt a binary variable that assumes value 1 if the product
is produced in period t…
0
votes
0 answers
Dynamic programming problem and optimal solution
For the following problem
\begin{equation}\max_{(\tilde{c}_t,\tilde{a}_{t+1+s})}\sum_{s=0}^{\infty}\beta ^su(\tilde{c}_{t+s})\end{equation}
s.t. the following restrictions
$\begin{equation}
\begin{split}
\tilde{c}_t&=(1-\delta…
Renzo GA
- 1
0
votes
1 answer
Dynamic programming-- chocolate bar
There is a chocolate bar that has $m\times n$ rectangles. In each step, we can break one piece to two ones along a line. Give a dynamic programming algorithm which computes the minimal number of breaks to “squareize” a $1 \times 1$ bar. Can someone…
Userabc
- 315
0
votes
0 answers
dynamic programming : maximize score
You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that…
0
votes
0 answers
I have a binary plot in some coordinate space, how do I find slope most efficiently?
So basically I have a 2d array filled with 1s and 0s. There should be a linear slope associated with the 1s, and I need to find that linear slope with the best accuracy and quickness possible.
How could I do this (please note, there could be…
Spaderdabomb
- 489
0
votes
1 answer
Cost function with stochastic variable
I'm not as well versed as I would like to be to confidently evaluate the following cost function. So any affirmation would be appreciated. Given an initial stage $x_0$
$$J_\pi(x_0) = \lim_{N \to \infty} \mathop{{}^{E}_{w_k}}_{k= 0,1,...,}…
Jack
- 463
0
votes
2 answers
Dynamic Programming Investment Question
I'm working on a dynamic programming problem from a textbook. My solution is different from that given in the solution manual, and I'm looking for input as to which answer is correct.
The problem is to choose between two investments ($A$ and $B$) at…
Malthus
- 353
-1
votes
1 answer
NxN grid traversal
Suppose I have a NxN grid (or matrix) and each entry has integers. There is a standard DP problem where you want to find the maximum sum path from top left corner and bottom right corner, using only 'down' and 'right' moves, which can be solved in…
Ted
- 365
-2
votes
1 answer
This is a dynamic programming question. Details can be found in the body(Including an image)
Write the optimal profit of the problem as a function of $z_{k}{(i)}.$
Solve $z_{1}(i)$ for all i ∈ {0,...,α}.
Write a recurrence equation satisfied by $z_{k}(i)$ for all (k,i) ∈ {1,...,n} × {0,...,α}.
For the first question, I wrote …
Ni Jiasheng
- 11