# Tag Info

## Hot answers tagged dynamic-programming

18

For the knapsack problem, you just use the Pisinger's code. It implements an exact algorithm, it is the fastest algorithm known in the literature, and it is open-source: http://hjemmesider.diku.dk/~pisinger/codes.html

10

There are a few courses on Coursera that offer such learning materials. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming (Intermediate) The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal ...

9

A comprehensive comparison of different approaches to solving the knapsack problem is given in the recent paper1 by Ezugwu et al., where the authors compare the performance of the following approaches both in small size and large size problems: Genetic algorithms, Simulated annealing, Branch and bound, Dynamic programming, Greedy search algorithm, ...

6

As it is explained here, this problem is a portfolio selection problem. The player should select the first $n$ booths with the maximum $E(g_i)=p_i \times r_i$ in which $E(g_i)$ represents the expected value of gain, then among the selected $n$ booths, the player should start playing the games from the one with maximum $r_i$. In other words, the selected ...

6

The "cost" values in the lower left table are calculated as the sum of the cost of buying the car ($12000$), plus the total maintenance cost of each year of owning the car, minus the trade in cost after the specified number of years has elapsed. So, the total cost of owning the car for one year is $12000$ (price of car) $+$ $2000$ (maintenance cost during ...

4

It looks like there is no relationship between different knapsacks, so you can solve this exactly as $m$ independent 0-1 knapsack problems. Also, for knapsack $j$, you can eliminate any items $i$ that have $p(i,j)\le 0$.

4

For the following I did not check in depth the rules related to end-of-period/beginning of period, so this is something you should carefully check for your problem. However, the approach does not differ much if this is incorrect (but your numbers may end up different). Sanity checks are definitely in order before you take this answer for granted! I think ...

4

You have an instance of the 0-1 knapsack problem where you want to determine which teams to select to maximize the number of wins, subject to a budget. The linked page provides a DP recurrence, which is obtained by conditioning on whether or not you select the next team. The optimal objective value for your instance is 28: \begin{matrix} \text{team} & ...

4

Disclaimer : this is more of a hint than a complete answer. You can use the following model as a starting point to make your own model. I am ignoring two items : Constraint from option 3: Under this option, he also must paint one year after the Option 3 repair at the same additional cost of $1M/boat. Surface area constraints You will have to tweak what ... 4 To my knowledge, the term relaxation is used to indicate that a constraint (or a group of constraints) is removed from the model, rendering a model that is more loose, less constrained. In the context of Lagrangian relaxation, a constraint (or group of constraints) is removed from the model, and added to the objective function with a coefficient (or more ... 3 For each state$s$, you want to compute the value function$V(s)$, which satisfies$V(0)=0$and the Bellman equation for$s \not= 0$: $$V(s) = \min_\mu\left\{1+\sum_z V(f(s,z)) p(z;\mu)\right\}. \tag{13}$$ The$\min_\mu$is over all legal actions$\mu$in state$s$. The$\sum_z$is over all outcomes$z$that can occur when action$\mu$is taken in state$s$.... 3 To get$O(2^M M^2)$instead of$O(M!)$, you could modify the dynamic programming formulation of the traveling salesman problem, with a state for each subset of booths visited so far. 3 The previous answer provided a great list on the classical dynamic programming. For Reinforcement learning and Deep Reinforcement learning, a wonderful online free course on RL by David Silver (the first author of the AlphaZero, AlphaGo algorithms) exists: YouTube links A more advanced course by Sergey Levine exists for free at: YouTube link For both ... 2 Just to expand very slightly the comments by Mark: in general exact stochastic dynamic programming scales quite poorly. Value iteration complexity for each iteration is$O(A S^2)$where$A$is the number of actions and$S$is the number of states. And the number of iterations goes up with the discount factor$\beta$as the worse case number of iterations is$...

2

You don't give that bit of information, but you might be able to use a far more efficient algorithm when knapsack size (let's call it $S$) is small enough (small enough to create an array of each possible value you could get) and all the items have positive (or zero) weight. For example, if maximum knapsack size is $10^7$ units, you could easily create an ...

2

There are algorithms specifically designed for shortest path problems, so dynamic programming is not the most common choice for it. On the other hand, small shortest path examples are commonly used to demonstrate DP (in part because they are easy to grasp). As for how to use DP here: If you are at 5, the least costly (not to mention only) path to 6 costs 7....

2

I do not understand why the formula for $C_{0,4}$ is as such. A simple check reveals that the unit on the RHS are pounds / (pounds / inch2) = inch2 whereas the unit for the cost is pounds. We have only three cases to consider here: 12'' shelf, 8'' shelf + 12'' shelf, 4'' shelf + 8'' shelf + 12'' shelf. The general formula for the total cost is given by \...

2

It's definitely the same idea. You can look at dynamic programming as developing a program to deal with large combinatorial problems, where brute force just isn't efficient. It comes down to finding a program that runs in polynomial time. And just like we like efficient solutions in OR, it's crucial to write efficient code when you are developing ...

2

The following model gives the purchasing temporal sequence for truck so that the cash flow is optimal within the planning horizon of 17 years. The model requires $68$ Boolean variables ($68=17 \cdot 4$) and $17$ integers variables (1 integer variable for each year). Every year will be designate by means of a pedice $k=1, 2, \cdots, m=17$. For each year the ...

1

From context, I'm assuming that the farmer always needs to have a truck, and the question is when he should replace it. For the constraints, you can formulate in terms of 17 binary decision variables: $x_1$ = "replace in year 1?", $x_2$ = "replace in year 2?", ...etc. "Cannot sell before it is two years old": i.e. cannot replace ...

1

In optimisation theory, creating a relaxation refers to an operation which: Creates a superset of an underlying set, if the operation is done on a set Produces a new set of functions that define a superset of a set associated with some original function (usually the feasible region). For instance, if I have a nonconvex function/set, I can create a convex ...

Only top voted, non community-wiki answers of a minimum length are eligible