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
2answers
42 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
67 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 ...
2
votes
0answers
21 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
19 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
18 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
84 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
36 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
19 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
48 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
0answers
34 views

Dynamic algorithm for minimum weight of a dominating set in a partial k-tree

Let $G$ be a graph with vertex-weights $w : V → \mathbb{R^+}$. A dominating set is a set $D$ of vertices in $G$ such that all vertices of $G$ are either in $D$, or have a neighbor in $D$. The ...
0
votes
2answers
72 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
11 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
12 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
31 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
42 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
155 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
95 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 ...
1
vote
0answers
42 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
18 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
101 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
29 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
34 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 ...
2
votes
0answers
66 views

Why no Forward Dynamic Programming in stochastic case?

Dynamic programming usually works "backward" - start from the end, and arrive at the start. This works both when there is and when there isn't uncertainty in the problem (e.g. some noise in the ...
0
votes
0answers
57 views

Bin Packing and Partition.

I am trying to do my assignment and got really confused and hard to understand with particular question. I need to show or prove that Partition ≤p Bin Packing. I read through the lecture slides and ...
0
votes
0answers
7 views

maximising non linear problems

X1=1/2(phi)-7/3X2 X2=7/8X1-3/8(phi) 3X1+6X2=72 Note: i lacked the symbol for phi so replace 'phi' with its symbol. also, the x in uppercase are not multiplication signs, but just X for unknown the ...
0
votes
0answers
74 views

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 ...
0
votes
0answers
27 views

Dynamic Optimization on Matlab

I have been working on the following (quite long but easy) dynamic optimization problem: $$ \max_{C_1} 2\ \sqrt[]{C_1} + \beta V_T(W_2)$$ Where $W_2$ is defined as follows: ...
2
votes
1answer
60 views

Dynamic programming: multiple subset sum

The subset sum problem is finding a solution $x \in \{0,1\}^n$ such that $$\sum_{i=1}^n a_i x_i = c,$$ for $a_i, c \in \mathbb{F_q}$ (also possible for $a_i,c \in \mathbb Z$). I know that there ...
0
votes
0answers
39 views

k'th best solution or Top k solutions to the 1-0 knapsack problem via dynamic programming

How do I find the k'th best solution to the 1-0 knapsack problem via the modification of the standard dynamic programming algorithm? LP solution will also be interesting. Thanks, Vladimir
0
votes
0answers
25 views

Partition Problem with discontiguous sets

I'm trying to solve a variant of the partition problem. I have two important twists. I need to solve for k partitions, not just 2, as in the classic partition problem. The following code does that: ...
0
votes
0answers
32 views

Problem involving joining up three sided shapes

You are given a collection of three sided shapes. They each have certain type of texture. 0 being rough and 1 being smooth. ...
2
votes
0answers
105 views

How to find expectation in this weird problem? (Pretty Interesting)

There are $N$ wires. The $i^\text{th}$ wire has $P_i$ bulbs. The bulbs are connected in series, so if you break a bulb, all the bulbs on the wire go out. A person can break any lit bulb with equal ...
1
vote
1answer
44 views

sub-series matching, graph matching

Let $A={a_{1}...,a_{N}}$ and $B={b_{1},...,b_{M}}$ be finite sets of integers, such that $N \geq M$. Find a mutually-exclusive covering of size $M$: $A_{1},...,A_{M}⊂A$ that is monotonic, meaning: if ...
0
votes
1answer
51 views

Is this function bounded or not?

$f(x) = \left(1-\frac ax\right)^2$ where both $x>0$, $a>0$ Is this function bounded? i.e. is there an M such that $f(x) ≤ M < \infty$ ? How can I figure this out? Thanks very much in ...
0
votes
0answers
19 views

Geers MPC metric - understanding magnitude error and phase error

It is regarding this question/subject Integrate two sets of Data and check similarity I'm applying the formulas mentioned [here]. But I still can't understand these error rates M and P. It is ...
0
votes
0answers
71 views

Dynamic Optimization - Transversality Condition for Infinite Horizon Case

When solving dynamic optimization problem such as $$ \max \int_0^\infty f(t,x,x')dt $$ $$ \ s.t. x(t_0)=x_0 $$ we can use the Euler equation to obtain a differential equation to solve. ...
0
votes
1answer
47 views

Is this algorithm for 3D spherical interpolation correct?

I am attempting to write a spherical interpolation algorithm for for the application of smooth 3D animation in a game. The scripting language that the game engine uses is Lua. It is often easier for ...
6
votes
0answers
53 views

Approximate Dynamic Programing - Discount Factor for Very Long Horizons

I want an optimal strategy for a very long time horizon, say $K=100000$. I have dynamic decision making problem where next state $x_{k+1}$ is determined by the probability distribution ...
0
votes
0answers
21 views

Dynamic Programming - Change in Control Variables

I have a question on DP. The problem is $V(x_t,y_t) = max\{u(k_t) + \gamma \log(x_t) + \beta V(x_{t+1}, y_{t+1})\}$ Subject to $k_t +y_{t+1} + p_{t+1}x_{t+1} = w_t + (1+r)y_t + p_t x_t$ and $c_t, ...
2
votes
1answer
30 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
1
vote
1answer
65 views

How to come up with this recurrence relation for putting p rooks in a m×n chessboard?

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position. (Two rooks attack each other if they are in the same row or same column) How many ways ...
1
vote
1answer
110 views

Probabilistic dynamic programming question

A gambler has 2 dollars. He is allowed to play a game four times and his goal is to maximize his probability of ending with at least 6 dollars . If the gambler bets $b$ dollars then with ...
3
votes
1answer
51 views

Dynamic programming recursion

In a book by Wayne Winston for operations research I found this question. Here's how I did it: Let $t$ be the no.of subjects to pass and let h be the no.of hours she has in hand for studying. ...
4
votes
1answer
181 views

Cover the grid graph with simple cycles

I have a two dimensional n x m grid graph. And I want to find in how many ways this grid can be covered with simple cycles (it can be a one cycle or it can be many ...
0
votes
0answers
33 views

How to do linear quadratic dynamic programming with non homogeneous quadratic equation

I am not well versed on matrix algebra and linear quadratic programming. I am wondering if it is possible to make a non-homogeneous equation into a homogeneous one. I need to make the following ...
1
vote
1answer
48 views

Special Palindromic String

A string of length $N$ can be made from $6$ characters $a$, $b$, $c$, $d$, $e$ and $f$. There are some rules to make such a string: 1) $b$ can not come directly after $a$. 2) $d$ can not come ...
1
vote
1answer
63 views

An Algorithmic approach to the secretary problem with unknown n

I've been reading about the secretary problem these days and I got the idea for the case when we know the number of applicants $n$ in advance. I'd like to know what would be an algorithmic approach ...
0
votes
0answers
18 views

Bounded Knapsackproblem Formula DP

I knew how the binary Knapsack works with Dynamic Programming. But, now I am interested. How does the recursive formula look like if I allow n€{0,1,2} of the same item to be in the Knapsack? The only ...
0
votes
2answers
132 views

A mathematical brain teaser in probability field

That is a brain teaser but it is also a mathematical problem in probability field. One day, a man have been trapped into a building which has 18 floors. Now, he want to leave the building but there ...
0
votes
1answer
33 views

Solving for max () in Viterbi algorithm

In simple terms, what is the proper way to solve for max. I am working with the Viterbi algorithm and am now stuck on how to solve this part of the equation. pc(G,2) = 0.3 + ...