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

Dynamic Programming Exam Question [on hold]

Please help me to formulate and solve this problem. My initial idea is to use a recursion but i'm unsure as to how to carry on. a) Formulate this problem as a dynamic program. b) Find the optimal ...
0
votes
0answers
17 views

Dynamical clock in If statement [on hold]

I am making a program in mathematica that (i) Dynamically updates the value of a variable. (ii)Test conditional statements on the variable or calculate Mod or coefficient. Here is the code. t3 = ...
1
vote
0answers
35 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
24 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
31 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
11 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
24 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
27 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
16 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
96 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
15 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
11 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
39 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
30 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
42 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
18 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
74 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
50 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
20 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
14 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
17 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
29 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
72 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
216 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
72 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
42 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
72 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
26 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
26 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
105 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
278 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
56 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
10 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
48 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
94 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
32 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 ...
2
votes
5answers
422 views

Find value of f(2013)?

Given a function $f(x)$ such that: $f(1) + f(2) + f(3)+\cdots+f(n) = n^2f(n)$ Find the value of $f(2013)$. It is given that $f(1) = 2014$. I tried attempting the question as a bottom-up DP, but ...
1
vote
2answers
131 views

Dynamic programming:Making a Change

I'm practicing problems on dynamic programming.The problem is as follows: You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so ...
0
votes
0answers
11 views

Dinamic programming for sum of two largest values from a Uniform parent

I must find a recursion formula to find the sum of two largest values from a Uniform parent [0,1]. I need dinamic programming but I don't know how to organize it.
0
votes
0answers
53 views

Dynamic programming for optimal maximum and optimal minimum

We have a sequence of $a_i$ and a choosing rule that is take the first number $x_t\ge a_t$. The definition is = $$ min\{ t|t \in \{ 1,2,\cdots,n\}\,\,,\,\, x_t\ge a_t\}$$ The sequence $a_i$ is ...
1
vote
1answer
34 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
1
vote
2answers
389 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
1
vote
1answer
109 views

Three dynamic programming techniques

I've noticed three terms that come up when I look at dynamic programming exercises. Binary choice - seen it in a weighted interval scheduling problem. Multiway choice - seen in a segmented least ...
0
votes
1answer
23 views

Finding the optimal solution

Find the optimal solution of the problem $$\min \Bigg \{ \int_0^1 [x^\prime (t)^2 + 2x(t)^2]e^t dt : x(0) = 0, x(1) = e - e^{-2}\Bigg \}$$ and the value of the minimum. Not sure how to approach this ...
1
vote
1answer
73 views

Can every optimization problem that can be solved by a greedy algorithm be solved using dynamic programming? Why, why not?

In other terms, is the set of optimization problems solvable using greedy algorithms contained fully within the set of optimization problems solvable by dynamic programming?
0
votes
1answer
112 views

Understanding Mathematical Symbols in Algorithms

Just a quick question here. I am working on an assignment for algorithms involving dynamic programming. Don't worry, this isn't a question about my assignment, just a question about understanding a ...
1
vote
1answer
69 views

How to convert mathematical programming problem to dynamic programming problem

Do not know how to approach this problem. The task is to convert the problem of mathematical programming: $\max(\prod_{i=1}^nx_i)$ $\sum_{i=1}^na_ix_i\leq c$ $c \gt 0, a_i \gt 0$ into a problem ...
1
vote
1answer
83 views

Dynamic Programming - how to minimize sum of distances

Let's assume that we're given the num[N], an array of N positive integers in an ascending order. For instance, let's assume that N=10, and num[N] is the following: 1 2 3 6 7 9 11 22 44 50 Let ...
1
vote
0answers
19 views

Finding groups with minimum mean deviation

Is there any algorithm that groups consecutive elements in an array that gives the minimum mean deviation. For example we are given an array a=[1,2,3,4,8,2,3,5] There can be many "consecutive" ...
0
votes
0answers
31 views

Seam Carving - Energy functions. How do they work?

I have been taking an interesting in dynamic programming and more specifically Seam Carving. For those who are not aware what this is, please look here and for some more detailed information here. If ...