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
1answer
18 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
12 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
46 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
50 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
14 views

Algorithm to find highest path in a DAG

Let it be $G=(V,E)$, a directed acyclic graph. We will define function $h:V\rightarrow R^+$, when h(v) is the height of v. Let it be path $P=(v_1,...,v_k)$. We will also define the height of a path ...
1
vote
0answers
57 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
16 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
28 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
63 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
72 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 ...
2
votes
0answers
46 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
31 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
56 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
62 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
85 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
26 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
87 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
38 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
84 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
79 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
33 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
69 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
209 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
104 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 ...
2
votes
0answers
62 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
22 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
119 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
37 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 ...
4
votes
0answers
92 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
60 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
102 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
36 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
87 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
48 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
31 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. ...