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

2
votes
0answers
16 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
42 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
81 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
22 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
51 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
14 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
24 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
17 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
26 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 ...
1
vote
1answer
24 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
25 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
19 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
50 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
12 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
20 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
22 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
13 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
35 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
70 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
57 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
37 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
71 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
68 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
31 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
30 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
20 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
88 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
100 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=...
0
votes
0answers
35 views

How to find the number of subsets with a given length and XOR?

I have A (0<A<500000) elements (up to 10^6) in the set. I need to find in how many ways can I remove a subset, the size of ...
4
votes
1answer
101 views

How to setup the correct transportation tableu for this Caterer Problem?

The problem said: A caterer must supply 110 napkins on Monday, 90 on Tuesday, 130 on Wednesday, and 170 on Thursday. The caterer initially has no napkins on hand. New napkins can be bought for ...
0
votes
1answer
250 views

Dynamic programming problem finding the subproblem

There are gas stations along the way at distance $a_1, a_2, \ldots , a_n$ from place A to place B. Filling up at gas station $a_i$ takes $m_i$ minutes. Your car can hold enough gas to go 100 miles, ...
1
vote
0answers
109 views

All combinations of matrix parenthesizations

I have this problem: Let $S$ be a set which is the domain with two operators $+$ and $*$ and an element $0$ such that: $+$ is a binary operator that is: associative commutative idempotent (that ...