# Questions tagged [dynamic-programming]

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.

564 questions
Filter by
Sorted by
Tagged with
1 vote
55 views

### Finding the most probable labeling that sums up to some integer

We know that solving the optimization problem such as $$\max_{y_1, \dots,y_n} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0$$ is easy and can be done via dynamic programming (...
1 vote
13 views

### How to assign a known number of different size of outbound packages, to a known (different) number of inbound deliveries?

I am trying to solve a problem that looks like the multiple knapsack problem, the multiple bin packing problem and the subset-sum problem, but isn't exactly one of them. Imagine a warehouse where 4 ...
• 13
18 views

• 951
1 vote
46 views

### Maximize the sum of weights of covered intervals

Suppose we are given n open intervals $(a_1, b_1)$, ..., $(a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
• 163
1 vote
14 views

### define max function when arguments and operators are given, and you have to decide only where to put braces

I have the following problem: Given a set of $n$ values, $x_1,...,x_n$, and $n-1$ operators between them (that is, we are given the formula $x_1 o_1 x_2 o_2 ... o_{n-1}x_n$), our objective function is ...
13 views

### Optimal policies and if we would always choose them

Suppose the value of a policy $\pi$ is defined as $$V^{\pi}(s) =E[R \mid s, a]$$ where $R$ stands for the return associated with following $\pi$ from the initial state $s$. Let an optimal policy be ...
• 13.2k
80 views

### Optimal stopping of a Poisson Process with a risky reward

I'm confident that there is a well-known solution to this problem, but I am having trouble finding a reference for it. I am also quite rusty on these kinds of problems, so I am having trouble solving ...