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.

Filter by
Sorted by
Tagged with
7
votes
2answers
126 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 ...
7
votes
1answer
88 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 ...
5
votes
1answer
84 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 ...
16
votes
3answers
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 ...
6
votes
0answers
139 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 ...
-2
votes
1answer
59 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 ...
6
votes
1answer
148 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 ...
5
votes
1answer
114 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. ...
10
votes
2answers
162 views

Optimal set order to maximize stochastic reward

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

Suggestion of some courses in sequential decision making

I am studying about sequential decision making and I am willing to know if there is any course which is recorded and is publically available covering topics in dynamic programming (DP), reinforcement ...