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
12 views

Find Unique Index for a Subset S

I'm looking for a way to assign a unique number to a particular subset of S. S is a set of n distinct integers from 1 through n. Now, take the set of all subsets of length k where order doesn't ...
2
votes
0answers
10 views

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

My system can be represented by the following state-diagram. The inputs to this FSM are correlated. This implies that I can no longer make "independent input" assumption. My question is: How ...
0
votes
0answers
15 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
23 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
18 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
21 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
21 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 ...
1
vote
0answers
14 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 ...
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
18 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. ...
3
votes
0answers
21 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
11 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
29 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
68 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
26 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
74 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
26 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
53 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
34 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
57 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
68 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
66 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
86 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
28 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
19 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
20 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
91 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 ...
0
votes
2answers
80 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 ...
0
votes
0answers
34 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
76 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
225 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
106 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 ...
3
votes
1answer
65 views

Constrained LQR with a fixed terminal state. Can MPC be applied to this problem?

I am interested in solving the constrained LQR problem with discrete finite time when the target $x$ value is given, but the final $u$ could be anything s.t. constraints. $$\text{minimize }J = ...
0
votes
0answers
24 views

Cheapest subgraph of a tree that contains any $k$ vertices?

Given a tree, I want to find the cost of the cheapest connected subgraph of it, which contains a particular node $v$, and $k-1$ other edges. Each vertex has exactly 1 or 3 children. My thought was ...
2
votes
1answer
122 views

Bellman Equation, Dynamic Programming, state vs control

I am proficient in standard dynamic programming techniques. In the standard textbook reference, the state variable and the control variable are separate entities. However, I have seen examples in ...
0
votes
1answer
40 views

Graph Traversal with Changing Weights

Suppose I have a 2D grid of vertices, where every vertex $v_i$ has a weight $w_i$. Given a starting vertex $v_0$, I want to find the path of length $n$ which minimises the summation of weights along ...
0
votes
0answers
37 views

What is the name for an algorithm which searches all paths in a graph, using a tree structure?

Suppose I have a graph, and given a node in the graph, I want to iterate through all paths of length $n$ starting at that node, and sum up the weights of all nodes along each of these paths. The ...