a
b
c
d
x
y
z
AC
i
Randomize
About Dynamic programming calculator
Solve investment-allocation problems using dynamic programming online with the F*/K* tableau and detailed step-by-step solution. with complete, detailed, step-by-step description of solutions, that solves linear-programming problems up to 20×20 in size with coefficients of this type: decimal numbers and fractions.
To start the calculation, you need to first enter the problem dimensions in the input fields at the very top of the screen, and also choose the desired operation from the side menu.
A little below you will find an input window where you need to enter the coefficients, constraints, and right-hand-side values using the keyboard. The input control panel is also located here, which simplifies work with LP problems and contains the following control elements:
- The first element allows you to expand the input window. This can be especially useful when the tableau does not fit completely on the screen. If the table is still not fully visible after expanding the window, you can change the scale using the + / - buttons;
- The second element copies the current problem input to the memory buffer. This can be useful when you frequently solve the same LP problem or need to transfer data between operations;
- And the last element pastes the previously copied input, which allows you to restore problem data in just a few clicks instead of re-entering it manually;
And further down you will find a toolbar that allows you to customize the calculator and make it easier to work with. It is visually divided into three parts, each of which is responsible for the following functionality:
- The first part lets you select the number format used when displaying the solution result. You can also turn off step-by-step comments if you already understand the method and only need to check your own calculations, or hide the step-by-step solution entirely if you only need the final answer;
- The second part contains buttons that let you modify the input table dimensions, clear individual coefficients or the entire input, and the main button with an equal sign that takes you to the solution screen. All these buttons are duplicated by keyboard shortcuts. Hover over a button to see the corresponding key in a tooltip. You can also use the arrow keys to move the cursor between input fields;
- And the last part allows you to choose the number of digits after the decimal point for rounding non-integer results. A live preview shows how the rounded values will appear;
What is Dynamic programming?
Dynamic programming is an optimization technique that solves complex problems by breaking them into simpler overlapping subproblems and storing intermediate results to avoid redundant computation. In the investment-allocation setting supported here, the goal is to distribute a fixed budget across several enterprises to maximize total profit, exploiting the principle of optimal substructure: the optimal allocation for stages 1 through k can be built from the optimal allocation for stages 1 through k-1.
How to solve an investment-allocation problem with dynamic programming?
Set up the stage-by-stage F*/K* table, where each cell F*(q, x) records the maximum profit achievable by investing x units across the first q enterprises. Start from the last enterprise and work backwards: for each stage q and each possible total investment level x, enumerate all valid splits between enterprise q and the remaining stages, and record the best. The optimal total profit is read from F*(n, total_budget), and the optimal allocation is recovered by tracing the K* decisions back through the table.
Example of solving an investment-allocation problem with dynamic programming
| x3 | x3 = 0 | x3 = 1 | x3 = 2 | x3 = 3 | x3 = 4 | F*3 | K*3 | F*4 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | ||||
| 1 | 0 | 3 | 3 | 1 | 0 | |||
| 2 | 0 | 3 | 4 | 4 | 2 | 0 | ||
| 3 | 0 | 3 | 4 | 7 | 7 | 3 | 0 | |
| 4 | 0 | 3 | 4 | 7 | 11 | 11 | 4 | 0 |
| x2 | x2 = 0 | x2 = 1 | x2 = 2 | x2 = 3 | x2 = 4 | F*2 | K*2 | F*3 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | ||||
| 1 | 3 | 6 | 6 | 1 | 3 | |||
| 2 | 4 | 9 | 9 | 9 | 1 | 4 | ||
| 3 | 7 | 10 | 12 | 11 | 12 | 2 | 7 | |
| 4 | 11 | 13 | 13 | 14 | 13 | 14 | 3 | 11 |
| x1 | x1 = 0 | x1 = 1 | x1 = 2 | x1 = 3 | x1 = 4 | F*1 | K*1 | F*2 |
|---|---|---|---|---|---|---|---|---|
| 4 | 14 | 20 | 19 | 17 | 12 | 20 | 1 | 0 |
| 1 | 6 | |||||||
| 2 | 9 | |||||||
| 3 | 12 | |||||||
| 4 | 14 |
Frequently asked questions
What problem does this dynamic programming calculator solve?
It finds the optimal allocation of a limited resource — such as investment capital — among several enterprises to maximize total return, using stagewise dynamic programming.
How does dynamic programming find the optimum?
It breaks the allocation into stages, one enterprise at a time, and applies Bellman's principle of optimality: it computes the best return for each remaining budget level and combines stage results into a global optimum.
Why does the first row represent zero investment?
Row 0 is the baseline of allocating nothing, which always returns zero. Keeping it explicit lets the recurrence compare "invest here" against "invest nothing here" at every stage.
How do I read the optimal distribution?
The final table shows, for the full budget, how much to allocate to each enterprise and the resulting total return — the allocation that no other split can beat.