Real dynamic programming example with Javascript

Recently I had the opportunity to apply one of the most versatile algorithmic techniques in a real example, dynamic programming.

Dynamic programming helps us to find an optimized solution for a problem. For this, it breaks the main problem into smaller problems and it uses the optimal solution for each problem to find the most optimal solution for the main problem. The best way to understand this is to see a case, expose the constraints, explain the process steps and see the final code.

The problem

We have a list of transactions, each transaction, each transaction has a benefit for running it and each one should be executed in a specific service. Each service has a cpu time assigned. And each time we get a list of transactions we also get an available cpu time.

Our mission is to find the best combination of transactions that could be executed in the cpu time we have. We consider the best combination as the list of transactions that together sums the maximum possible benefit.

The list of transaction will be something like

[ {benefit: 100, service: 'one', id: 'xd-ftg'}, {benefit: 50, service: 'two', id: 'dfx-ffg'}, ...]

We will also have a fixed map of services and cpu time for each one

{one: 3, two: 1,...}

The solution

At first we can think, ok, if I need to find the best combination, I have to find all of the possible combinations that, in total, does not exceed the available cpu time, and pick the one with the max amount of benefit.

Creating all possible combinations sounds like something hard and also time consuming, and the larger the list of transactions, the higher the time will be. Also, could you imagine how many times we will perform the same calculations (list of elements that could fit together)?.

This kind of problem should be solved by creating a matrix with all the elements and a topic that we pick for the case. In this case, our matrix will be based on the list of transactions and all the possible cpu times (if the max cpu time we have is 50, we will have values from 1 to 50).

Some things to take in care for creating this matrix are:

• the transactions should be ordered from lower cpu time to higher o will won’t have calculated lower values when we need it.
• instead of starting at 1, we can start at the lowest cpu time for our services.

This could be our final (pre-filled) matrix.

Now, how to fill the matrix?. The first line is the easiest one:

• for each cpu time we will see if the transaction could be executed in the available time
• if it could be executed, we can save the value in the list of selected transactions
• if it could not be executed, we left the cell empty

The next lines (transactions) will follow all the same process for each cpu value):

• for each cpu time first, it will check if the transaction could be executed in the available time.
• if it could not be executed, the position will be filled with the value in the previous row.
• if it could be executed, there will be several validations. First, is there any cpu time for other transactions? If not, we make a comparison with the value in the previous row, does this new value have a better benefit than the value in the previous row?. If it has a better value, its value will be used. If not, the cell will be filled with the value in the previous row.

• but if there is cpu time available for other transactions, we are going to find the value to fill this cpu time. For this we take the cpu time for the cell, subtract the actual required cpu time and then look in the previous row for the value for the available cpu time and the final value will be the actual value + the found value. Example: cpuTime(6) — transCpuTime(3) = 3 => find in the previous row the cell which holds the value for cutTime as 3.

• that would be the process for all the remaining transactions.
• the final value will be the last filled cell in the matrix

You can find an example in this github repository. You can copy and change any part to make your own tests.

I hope this helps understanding dynamic programming techniques and give you an idea of what kind of problems you can solve with this. Feel free to leave any comment, it’s always welcomed.

Thanks for reading.