Tag Info

Solving a knapsack problem with a lot of items

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/~...
• 1,244

Suggestion of some courses in sequential decision making

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 ...
• 5,191

Solving a knapsack problem with a lot of items

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 ...
• 8,340
Accepted

Optimal set order to maximize stochastic reward

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 ...
• 8,340
Accepted

Dynamic programming example

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 ...
• 1,769
Accepted

Dynamic program for knapsack in $O(W)$ space?

There is a recursive scheme which makes it possible to retrieve the optimal solution with an $O(n + W)$ memory. It is described in Section 3.3 of the book "Knapsack Problems" (Kellerer et al....
• 1,711

Efficiency of Forward vs. Backward Recursion in Dynamic Programming

First, what is Dynamic Programming? Everyone has its own definition. The one I use is "Solving a problem recursively, while storing the results of the sub-problems to avoid recomputing them ...
• 1,711
Accepted

• 31.1k
1 vote
Accepted

Formulate a problem as Mixed Linear Programming problem

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: ...
• 1,767
1 vote

The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

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 ...
• 11.2k

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