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
15 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
31 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
29 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
35 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
0answers
69 views
+50

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
9 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
29 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
10 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
94 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
19 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 + ...
1
vote
0answers
34 views

Determining the optimal cost through dynamic programming.

There are $n$ houses numbered $\{1, 2, 3, \dots, n\}$. The cost of laying a cable that serves houses $j, j+1, j+2, \dots, j+k $ is $f (j, k)$. One cable can serve a maximum of 10 houses. The ...
1
vote
1answer
21 views

A clarification regarding dynamic programming.

This is a question regarding dynamic programming. The document to which I am referring is this (pg 325). It says that $$v_n(s_n)=\text{Min}\{t_n(s_n)+v_{n-1}(s_{n-1})\}$$ Here $v_n(s_n)$ is the ...
0
votes
0answers
33 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
0
votes
0answers
23 views

Can someone help me to get the mathematical formula for below scenario?

There was a question in topcoder, and its given below.I had a glance at the source code,but i didn't understand anything. Can someone help me to get the mathematical background or formula behind this ...
0
votes
1answer
52 views

The Change-making problem algorithm proof (at the dynamic programming method)

I saw here the algorithm for the "Change-making problem" (at the dynamic programming method). I saw it here: http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf I'm trying to find a ...
1
vote
0answers
45 views

kalman filter matrices

I would like to apply a kalman filter on data I receive from a sensor, i.e. a lightsensor. I have 3 light sensors, 1 for each axis. I am grouping all the data from the three sensors in 1 formula. My ...
2
votes
1answer
41 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
1
vote
1answer
33 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
0answers
18 views

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

How to solve problem using dynamic programming

How to solve this problem using dynamic programming: The company produces five types of electronic games (E1, E2,..., E5) and five types of mechanical toys (M1, M2,..., M5). On the market ...
0
votes
0answers
35 views

How do I compute the expected value of a function of two correlated random variables?

I'm trying to figure out how to properly compute the expected value of a function of two random variables and constants. The two random variables determine the state transitions in an MDP: The states ...
1
vote
0answers
22 views

Optimal Stopping Problem (With looking backwards)

Say you are trying to sell a good at the highest price. You draw independently from $F(p)$. The history of observations is $P = \{p_1, p_2,\dots\}$. Observing the $i$th price costs $c_i$, where the ...
5
votes
1answer
99 views

Two pawns walking in a complete graph

We have a complete graph $G = \langle V,E\rangle$ with non-negative values on edges. Let $C = \{v_1,v_2,\ldots,v_n\}$ be an ordered collection of $G$'s vertices. At the beginning we have two pawns in ...
1
vote
0answers
18 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
0
votes
0answers
16 views

Spin-off of Scheduling Weighted Interval Problem

I'm trying to solve a problem in which, given a + sign shaped area of land (with no width) and a list of contiguous sections of the land (segments, T-shapes, smaller + shapes, etc), each with an ...
0
votes
2answers
52 views

Find Algorithm, given a list of arcs, that maximizes number that fit on a circle

I'm trying to find an optimal algorithm that, given a list of arcs $(x_i, y_i)$, where $x_i$ and $y_i$ are the starting and ending angle measurements of the arc in radians, maximizes the number of ...
2
votes
1answer
68 views

How to do continuous-time Bayesian updating?

I am reading a game theory lecture notes. Some parts involve a continuous time Bayesian updating computation which I didn't really understand. There are two states $\{Good,Bad\}$. At time t people ...
1
vote
3answers
68 views

Finding the formula for summation of the series

I was just solving a competitive programming question, wherein I found out that a formula can be used for solving it efficiently. Problem statement: http://www.spoj.com/problems/TOHU/ I tried a lot to ...
0
votes
0answers
19 views

Approach for this Popular Algorithmic Problem

Given a matrix we have to select one value from each row so that the total value cost selected is minimum. Now the problem is we cannot select column "0" to "J" in "I"th row if we have selected ...
4
votes
1answer
78 views

Integrate two sets of Data and check similarity

I have the following CSV Data I used Excel Charts to plot the Data I want to compare these Data with other Data, in another word i want to comapre 2 curves and check the similarity between them in ...
0
votes
2answers
58 views

Minimize a non-convex function subject to linear dynamics constraint

I want to solve the following problem: $$\min\limits_{\bf u} \frac{\bf c^T {\bf x} (T_f)}{\| \bf c\|\|{\bf x} (T_f)\|}$$ subject to $$\dot{\bf x} (t) = A {\bf x}(t) + B {\bf u}(t)$$ $$x(0) = x_0$$ ...
2
votes
1answer
24 views

Explanation of strategies in infinite horizon dynamic programming problem

My question is regarding the Bellman equation regarding strategy $\sigma^{(1)}$ on the last 2 lines (I have attached pictures of the book below). If we know that all future states will have value of ...
1
vote
0answers
16 views

Scheduling problem

Consider the following setting: $N$ jobs, each has a starting time, which is assumed to be a natural number and all N numbers are distinct, e.g., the 1st job has starting time at 5, the 2nd is 6, the ...
0
votes
0answers
23 views

Pyramidal TSP without weight

Say $G=(V,E)$ with $V=\{1,...n\}$ and $l(i,j)$ is the distance of arc $(i,j) \in E$. The aim is to find a pyramidal path in $V$ with minimal length. A pyramidal path is a sequence of vertices $(n,i_1, ...
0
votes
1answer
35 views

Greedy choice property

There are two versions of the Knapsack problem, the integer and the fractional one. The difference between the integer and the fractional version of the Knapsack problem is the following: At the ...
0
votes
1answer
113 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
-5
votes
1answer
221 views

Are the propositions right?

I want to choose if the following propositions are true or false and justify the reason for the choice. Polynomial: good, exponential: bad. Radix Sort works correctly if we use any right sorting ...
1
vote
1answer
81 views

Count connected components after $M$ marbles removed

There are $N$ marbles in a line, numbered $1$ through $N$ from left to right. We need to count numbers of ways to remove exactly $M$ marbles such that there are exactly $C$ remaining connected ...
0
votes
0answers
51 views

Setting up the Bellman equations for dynamic programming

I have the following question I want to understand. The owner of a chain of three grocery stores has purchased five crates of fresh strawberries. The estimated probability distribution of ...
2
votes
1answer
103 views

Why does the Hamilton Jacobi Bellman Equation imply Pontryagin's Minimum Principle

I'm having difficulty understanding the proof that allows us to go from the Hamilton-Jacobi-Bellman equation to to the Pontryagin Min(Max) Principle. Lets consider $x(t)$ and $u(t)$ as real valued ...
2
votes
0answers
30 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
1answer
31 views

Optimal schedule for a set of jobs

Assume that yo have a set of jobs in which each has only a processing time that you need to minimize the sum of the completion (finish) times. Prove that your schedule is optimal. The wording throws ...
0
votes
1answer
112 views

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 ...
1
vote
1answer
320 views

Minimum cost to convert string S to good string

Given a string $S$ of $0$ and $1$ we need to convert it into a good string. A string is called good if and only if : Their are no two or more $0s$ or $1s$ together. It means $001$ is not good but ...
0
votes
2answers
98 views

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

Minimizing handling costs in the one-to-one TSPPD

Currently I'm reading about the Traveling Salesman Problem with Pickups and deliveries. This is similar to the classical TSP but there are $n$ requests and each request has a pickup location and a ...
0
votes
0answers
53 views

Define a maximization problem as an optimal stopping problem

We work over $\mathbb{R}_+^L$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that changes each time slot. To each vector ...
4
votes
1answer
112 views

Expected outcome for repeated dice rolls with dice fixing

Here is another dice roll question. The rules You start with n dice, and roll all of them. You select one or more dice and fix them, i.e. their value will not ...
0
votes
1answer
35 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...