# Questions tagged [dynamic-programming]

For questions about dynamic programming, a mathematical optimization technique where the optimal solution to the problem is found by breaking it down to simpler sub-problems and solved recursively.

12 questions
Filter by
Sorted by
Tagged with
231 views

### Multi-period linear dynamic programming with differing in-period dependencies and changes

I’m not sure if I’m wording this right but in a nutshell, my problem is: I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
122 views

### Formulate a problem as Mixed Linear Programming problem

I need to formulate the following problem as a Mixed Integer Linear Programming problem A farmer needs to establish a 17-year business plan where he will decide when to sell or buy a new truck. The ...
253 views

### The general meaning of “constraint relaxation” in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
108 views

### Dynamic programming example

I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK for the next 4 years. I am considering the possibility of being a customer of company A which sells ...
187 views

### Solving a variant of multiple knapsack problem/ generalized assignment problem

Consider $m$ knapsack and $n$ items. With each knapsack $j$ associated a capacity $c(j)$ and with each item $i$ associated a profit $p(i,j)$ (that depends on the knapsack, so it's not exactly the ...
3k views

### Solving a knapsack problem with a lot of items

I am wondering what are the fastest ways(faster than classical dynamic programming) to solve the knapsack problem (to optimality) with $n$ items when $n$ is nearly equal to $10000$ ? Apart from ...
143 views

### Minimization of car cost during 4 years problem

I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK for the next 4 years. I am considering the possibility of being a customer of company A which sells BMW ...
62 views

### dynamic programming shortest path example

Could someone please show how he uses dynamic programming to solve for minimum cost of getting from 1 to 6? Is it recommended to use dynamic programming to solve this? Edit: I know that dynamic ...
158 views

### Dynamic programming problem with machines

A company will be using a new technology for 5 years. For this purpose a specialized machine is required. The company currently has one, which will be 2-year old at the beginning of next year. The ...
347 views

### Minimisation of shelving cost problem

A library must build shelving to shelve $200$ 4-inch high books, $100$ 8-inch high books, and $80$ 12-inch high books. Each book is 0.5-inch thick. The library has several ways to store books. ...
You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth ...