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.

learn more… | top users | synonyms

1
vote
0answers
19 views

Optimal Apple Eating Strategy

You hate apples. As a result, you have angered the apple king and are being punished. You will have to eat $n$ apples before the apple king is willing to let you leave. The apples are marked from $1$ ...
1
vote
0answers
13 views

Pontryagin's maximum principle

So I've been doing some optimal control theory lately. It's really interesting but I've spent the whole day trying to wrap my head around pontryagin's maximum principle. There's a lot of mathematical ...
0
votes
1answer
44 views

Maximum Coin Changes That Does Not Add To a Dollar

What is the maximal amount of money attained from coins of 1, 5, 10, 25 cent denominations that none of its subset amounts to 100 cents? We can find the solution with exhaustive or naive dynamic ...
1
vote
0answers
14 views

How is the system equation formulated? [Resource Allocation Problem]

I do not find how the following system equation is formulated. The following example is about the Deterministic Continuous-Time Optimal Control chapter. We are considering a continuous-time dynamic ...
2
votes
0answers
18 views

Minimum number of Coins needed to make change?

I was trying to solve the one particular problem and I ended up reading this. I read this question Above link states the problem of changing the amount when coins are given in infinite amount. ...
1
vote
1answer
49 views

Why does the “printing neatly” algorithm use cubes rather than squares?

In Introduction to Algorithms, 2nd ed. (Cormen, Leiserson, Rivest, and Stein), ch. 15, Dynamic Programming, problem 15-2 Printing neatly (a copy of which is here), the official solution given in ...
2
votes
1answer
90 views

Given a population of fish with exponential growth, what is the optimal strategy for fishing?

Suppose we have a population of fish, say $10000$, with an exponential growth each year of $30\%$. If we want to collect as many fish as possible in, say 10 years, a natural question to ask is: ...
1
vote
1answer
24 views

concise book on MDPs with stress on solving them using DP

What is a good book for MDP with a stress on solving them using DP? However, the book should stress on the theorems and proofs and make a case for why DP is the most popular tool to solve MDPs. I am ...
-1
votes
1answer
55 views

$L\in P$ prove that $L^*\in P$

I have that question that looks kinda easy at first but it is quit hard. Let $L\in P$ prove that $L^*\in P$ (L is a language and P is the class of all problems which can be decided by a ...
0
votes
0answers
16 views

Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
3
votes
0answers
30 views

How to handle Finite-state-machine with correlated inputs?

My system can be represented by the following state-diagram. where each arch represents Input/Output when a transition is made from one state to the other. The inputs to this FSM are correlated. ...
0
votes
0answers
19 views

Dynamic Programming problem with extremely high dimension over 1000

I am dealing with a dynamic programming problem with extremely high dimension. Currently, I know some methods like Smolyak algorithm and Adaptive sparse grid method. They can solve problem with ...
0
votes
0answers
79 views

Help me to solve $\overline{abc} \cdot d +\overline{ef}\cdot g + h \cdot i = 2010$

The problem is: $$(a \cdot 100 + b \cdot 10 + c ) \cdot d + (10\cdot e + f ) \cdot g + h \cdot i = 2010$$ and $$\{a, b, c, d, e, f, g, h, i\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}.$$(not allowed to repeat). ...
2
votes
2answers
31 views

Programming Bifurcation analysis

Next year I'm going to do my final project for graduation. I've been assigned to search and study some biomathematical models with bifurcation theory and numerical bifurcation analysis. I'm thinking ...
0
votes
1answer
28 views

LQR problem with interaction term between state and control

Consider the usual linear process $x_{t+1} =Ax_t+Bu_t+Cw_{t+1}$ where $w_t$ is an independent and identically distributed $N(0,I)$ process. The objective is $$ V=E\sum_{t=0}^\infty \beta^t(x_t'Qx_t + ...
2
votes
0answers
26 views

Strategy for selling/buying a stock by average reward value iteration

At beginning of any day $t$, I may own $0$ or $1$ share. The price of the share follows the Markov chain in the table below. At the beginning of a day where I own a share, I may either sell at today’s ...
0
votes
0answers
35 views

Number of ways to multiply n matrices?

I keep thinking about this problem in terms of factorials. That is at first you can choose between n matrices, then n-1, then n-2 and so forth. Which gives you $n*(n-1)*(n-2) *... *1 = n!$ ways to ...
1
vote
1answer
20 views

Knapsack for table

I have a problem that I can't solve. There is this table. I have to optimaly allocate 1 million dollars among the five products. I think it looks like knapsack problem but I am not sure. If I want to ...
0
votes
1answer
22 views

r-combination from n objects where objects can be indistinguishable or distinguishable

How to solve this kind of combinatorial problem. You are given n objects and you have to find out r-combination from it. As example there are 4 objects.. 1 2 2 3..you have to find out how many 3-...
1
vote
0answers
16 views

Minimum sum in an array with constraint

I am a newbie to the dynamic programming paradigm.. while trying to solve this question....... How to find minimum sum of the numbers in an given array such that at least one of three ...
1
vote
1answer
51 views

calculate price based on demands and maximize revenue

I believe I have a simple question which I am struggling to answer. It is as follows: We have 400 items, each item costs £100. Retailer bought these items before the season started. The forecasted ...
0
votes
1answer
53 views

Max $z = x_1(1-x_2)x_3$ s.t. $x_1 - x_2 + x_3 \le 1$

Using dynamic programming, Maximise $$z = x_1(1-x_2)x_3$$ subject to $$x_1 - x_2 + x_3 \le 1$$ $$x_1, x_2, x_3 \ge 0$$ Here's the outline of my solution 1. How is it? Let $y_2=...
0
votes
0answers
17 views

Algorithm to Find Highest Path in a Directed Acyclic Graph

Let $G=(V,E)$ be a directed acyclic graph. We will define the function $h:V\rightarrow R^+$, where h(v) is the height of v. Let $P=(v_1,...,v_k)$ be a path. We will also define ...
1
vote
0answers
58 views

number of strings which differ at atmost n positions?

I have been given a string T comprised of only 's','t','u','v' as characters . I want to find numbers of strings with length |T| which differs at atmost n position from T. Also each such string must ...
0
votes
0answers
14 views

Is there an analytic solution to this dynamic programming problem?

I have a optimal growth problem,$$V(k_{t}) = \max_{c_t,k_{t+1}} \left\{\sum_{t=0}^{\infty}{\beta}^{t}U(c_{t}) \right\},$$ the utility function is isoelastic: $U(c_t)=\frac{c_t^{1-\sigma}}{1-\sigma}.$ ...
0
votes
0answers
22 views

Does the existence of a Algebraic Riccati Equation implies the existence of an functional minimization?

Let $\forall k\ge 0. V_k(x)$ be the value function related to the recursive optimization problem $ J(x_0) = \underset{u}{\inf} \sum_{k=0}^{N-1} x_k^T Q x_k + u_k^T R u_k + x_{N}^T P_N x_N \\ s.t. x_{...
3
votes
0answers
23 views

Finding optimal connections between elements of set

I'm a $3$rd year Math undergrad and I decided to take an algorithms extra class. This question was a bonus one on my mid-term and I still have no idea on how to approach it. Given an array solely ...
0
votes
0answers
14 views

separability of dynamic programming

I am working on some portfolio selection problem and running into this concept. It is stated that "multiperiod mean–variance formulations cannot be solved using dynamic programming due to their ...
0
votes
0answers
40 views

How to discretize state space with uniform grid

Let us consider a general continuous time stochastic differential equation represented by *dx* = A(x)dt + B(x)udt + $\sigma$ dw where A(x) represent the ...
3
votes
2answers
72 views

An Interesting Probabilistic Game

I heard this brainteaser from someone else and found it is interesting. Can someone help me on solving this problem? Thanks so much for your help... There are n slots totally. You have access to ...
0
votes
1answer
14 views

Algorith/Method to determine if a percentage will be greater than fixed amount without knowing the final number.

If you are applying a discount to a price and you have two possible choices on the discount to apply, a percentage or a fixed amount, e.g. I could remove a fixed amount of 5 or I can remove a 20% of ...
1
vote
1answer
27 views

Books of combinatorics, with dynamic programming

Does anybody recommend a good book of combinatorics, especially with a lot of dynamic programming techniques? I'm looking for something really advanced, as I'm just finishing my undergrad in computer ...
3
votes
2answers
76 views

Fill the segment with circles

There is a line. On this line, we have $N \le 100$ points $(x_1, x_2, ..., x_n)$, $0 \le x_i \le 10^8$ which are centers of circles. We want to choose such radii for those circles, but in such way ...
2
votes
0answers
28 views

Discrete Optimization Problem (VRP)

Consider the following setting : We have two pickup nodes (a) and (b)and two delivery nodes (c) and (d). At each pickup node, there are entities to be picked up and delivered by cars (n cars) to ...
3
votes
1answer
62 views

What is the difference between moving-horizon DP and MPC?

What is the difference between moving-horizon DP (dynamic programming) and MPC (modelbased predictive control)? In both cases, the system input at time $t$ is determined by solving a finite-time ...
0
votes
0answers
38 views

Rearrangement algorithm

I came across the following algorithm puzzle while interviewing for computer programmer job with a top internet giant. There are $n=4$ bags with each bag able to carry a maximum of $k=500$ Kilogram ...
2
votes
1answer
58 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
1
vote
1answer
72 views

Find minimum number of coins with Largest value coins?

There is a greedy algorithm for coin change problem : using most valuable coin as possible. How We can find a quick method to see which of following sets of coin values this algoithms cannot find ...
1
vote
2answers
72 views

Solving the devil's penny puzzle

I was reading an article about the devil's penny puzzle. We are given $n$ boxes, one of which contains the devil's penny while the others contain an amount of money $a_1,\ldots,a_{n-1}$. These numbers ...
0
votes
0answers
90 views

maximum frequencies of numbers in a matrix

I have a matrix A of size n*n.Consider a new matric M : M[i][j]=max of frequencies of numbers occuring in ith row and jth column(A[i][j]) counted once. I have a ...
3
votes
0answers
32 views

Stock Price Dynamics correlated with Bond market returns

I am currently working on to derive the following form of the stock price dynamics: $$dS_t = S_t[(r_t + \psi\sigma_S)dt + \rho \sigma_S dz_{1t} + \sqrt{1-\rho^2}\sigma_S dz_{2t}$$ where the ...
0
votes
0answers
33 views

Integer partitions with distinct parts

Let $~~p(n)~~$ denote the number of all partitions of positive integer $~~n~~$ with distinct parts. I would like to find some effective algorithm for calculating $~~p(n)~~$. It seems that dynamic ...
0
votes
2answers
22 views

Maximum profit by optimizing assignment

So a company has n available projects and k employees on the bench. Each project has a "number of hours" associated with it. Each employee has an hourly rate that the parent company gets paid gets ...
0
votes
1answer
89 views

Explanation of formula

Suppose that we have $M$ production stations $A_1, \dots, A_M$ of a product and $N$ destination stations $B_1, \dots, B_N$ of the product. We suppose that $x_{ij}$ units of the product are ...
0
votes
1answer
39 views

Find two integers that satisfy a property

The finite sequence of integers $Y_1, \dots, Y_M$ takes both positive and negative values, where $M$ is a fixed positive integer. Could you help me to find a formulation using dynamic programming that ...
0
votes
1answer
22 views

Minimal sum of non-consecutive elements

I have $N$ numbers $a_i$. I want to find the smallest sum of EXACTLY $K$ non-consecutive elements. I know how to solve this in $O(N*K)$ (straightforward dynamic programing) but it is too slow. Anyone ...
1
vote
1answer
115 views

Dynamic programming at a non linear programming problem

Could you explain to me how we can use dynamic programming in order to solve a non linear programming problem? What do we do for example if we are given the following problem? $$\max (y_1^3-11 y_1^2+...
0
votes
2answers
81 views

Converting Java Code to Mathematic formula

I have algorithm , but I don't know how to convert it to mathematic formula. ...
0
votes
0answers
13 views

Show that there is a critical transition probability (2 discrete states)

Let $\beta$ be a fixed constant (it isn't specified that $\beta <1$, but assuming it is okay if it is necessary), and $u$ be some function from $W\to \mathbb{R}$. Let there be two discrete states, ...
0
votes
0answers
13 views

time complexity of a tree dynamic programming problem

The original problem: http://codeforces.com/blog/entry/20508 581F — Zublicanes and Mumocrates, I want to prove that the time complexity is $O(n^2)$. Suppose we have a tree, how to prove that $\sum_{v=...