Topic:

Ten workers

Five gold mines, with the corresponding revenue and required workers for each mine as follows

400kg/5 people 500kg/5 people 200kg/3 people 300kg/4 people 350kg/3 people

Every gold mine must be dug entirely or not dug at all, and you cannot send half the men to dig and take half the gold

Seek the best gold yield

stag1

For every gold mine in question, there is a choice between “dig” and “don’t dig”,

Then, for 10 workers and 5 gold mines, 400kg/5 people, 500kg/5 people, 200kg/3 people, 300kg/4 people, 350kg/3 people, the optimal profit can be converted into:

Last gold mine: 7 workers 4 gold mines 400kg/5 people 500kg/5 people 200kg/3 people 300kg/4 people + last gold mine 350kg

The last gold mine not to be dug: 10 workers 4 gold mines 400kg/5 people 500kg/5 people 200kg/3 people 300kg/4 people

The maximum payoff in both cases

Similarly, further conversions can be made for the first four gold mines

7 workers 4 gold mines 400kg/5 people 500kg/5 people 200kg/3 people 300kg/4 people can be converted to

Last gold mine: 3 workers 3 gold mines 400kg/5 people 500kg/5 people 200kg/3 people + last gold mine 300kg

The last gold mine not to be dug: 7 workers 3 gold mines 400kg/5 people 500kg/5 people 200kg/3 people

10 workers 4 gold mines 400kg/5 people 500kg/5 people 200kg/3 people 300kg/4 people can be converted to

Last gold mine: 6 workers 3 gold mines 400kg/5 people 500kg/5 people 200kg/3 people + last gold mine 300kg

The last gold mine not to be dug: 10 workers 3 gold mines 400kg/5 people 500kg/5 people 200kg/3 people

Similarly, the above four cases can be further divided, so the problem is divided into two, two into four, and the problem is simplified to the optimal choice when there are zero gold mines or zero workers. At this time, the profit is zero, which is also the boundary of the problem

This is the point of dynamic programming: to determine the relationship between the global optimal solution and the optimal substructure, and the problem boundary

This relationship, when expressed in a mathematical formula, is called the state transition equation

Set the number of workers as W, the number of gold mines as N, the content of gold mines as array G, and the number of people required for gold mining as array P

F(n, w) is the optimal income function for n gold mines and W workers

Is:

Problem boundary, when the number of gold mines is 0 or the number of workers is 0

F(n, w) =0 (n=0 or w=0)

When there are not enough workers left to dig the current gold mine, there is only one optimal substructure

         F(n, w) = F(n-1, w) (n>=1, w<p[n-1])

In general, there are two optimal substructures

        F(n, w) = Max(F(n-1, w), F(n-1, w-p[n-1]) + g[n-1]) (n>=1, w>=p[n-1])

The decomposition diagram of the state transition equation is as follows

Mapping connection

According to the state transition equation, the code is as follows:

@param {Array<number>} p @param {Array<number>} @param {Array<number>} Function getBestColMiningV1(w:number, n:number, p:Array<number>, g:Array<number>):number { if(w === 0 || n ===0) { return 0 } if(w < p[n-1]) { return getBestColMiningV1(w, n-1, p, g) } return Math.max( getBestColMiningV1(w, n-1, p, g), getBestColMiningV1(w - p[n-1], n-1, p, G) + g[n-1])} console.log(getBestColMiningV1(10,5, [5,5,3,4,3], [400, 500, 200, 300, 350])Copy the code

If the time complexity of this algorithm is O(2n) in the case of sufficient workers, there are two cases in each mine

Stag2

Analysis of the above breakdown diagram shows that

F(2,7), and its subbranches, are computed twice with the same parameters. The current number of gold mines is 5. As the number of gold mines increases, the repeated calls must increase

How to optimize this problem requires the introduction of another core point of dynamic programming: bottom-up solution

Start by creating a table to document the intermediate process of selecting a gold mine

The table on the far left represents the different gold mines, from top to bottom, and each additional row represents one more alternative gold mine, which is the n value in F(n,w)

The top of the table represents the number of workers, from one worker to ten workers, which is the value of W in F(n,w)

The blank grid represents the best payoff given n workers and W gold mines, which is F(n, w)

We can start with row 1, column 1, and try to fill the blank space based on the state transition equation:

As w < p[n-1], the corresponding state transition equation of the first four cells in the first row is as follows:

        F(n, w) = F(n – 1, w) (n>1, w<p[n-1])

Substitute to solve:

        F(1, 1) = F(1-1, 1) = F(0, 1) = 0

        F(1, 2) = F(1-1, 2) = F(0, 2) = 0

        F(1, 3) = F(1-1, 3) = F(0, 3) = 0

        F(1, 4) = F(1-1, 4) = F(0, 4) = 0

For the last six cells in the first row, since W >= P [n-1], the corresponding equation is as follows:

        F(n, w) = Max(F(n-1, w), F(n-1, w-p[n-1]) + g(n-1)) (n>1, w>=p[n-1])

Substitute to solve:

        F(1, 5) = Max(F(1-1, 5), F(1-1, 5-5) + 400KG) = Max(0, 400KG) = 400KG

         F(1, 6) = Max(F(1-1, 6), F(1-1, 6-5) + 400KG) = Max(0, 400KG) = 400KG

         F(1, 7) = Max(F(1-1, 7), F(1-1, 7-5) + 400KG) = Max(0, 400KG) = 400KG

        F(1, 8) = Max(F(1-1, 8), F(1-1, 8-5) + 400KG) = Max(0, 400KG) = 400KG

        F(1, 9) = Max(F(1-1, 9), F(1-1, 9-5) + 400KG) = Max(0, 400KG) = 400KG

        F(1, 10) = Max(F(1-1, 10), F(1-1, 10-5) + 400KG) = Max(0, 400KG) = 400KG

The first four of the second line are the same as the first line. Since W < p[n-1], the state transition equation is:

        F(n, w) = F(n – 1, w) (n>1, w<p[n-1])

Substitute to solve:

         F(2, 1) = F(2-1, 1) = 0

        F(2, 2) = F(2-1, 2) = 0

        F(2, 3) = F(2-1, 3) = 0

        F(2, 4) = F(2-1, 4) = 0

Similarly, in the first line, since w >= P [n-1], the state transition equation is:

        F(n, w) = Max(F(n-1, w), F(n-1, w-p[n-1]) + g(n-1)) (n>1, w>=p[n-1])

Put into the solution:

         F(2, 5) = Max(F(2-1, 5), F(2-1, 5-5) + 500KG) = Max(F(1, 5), F(1, 0) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 6) = Max(F(2-1, 6), F(2-1, 6-5) + 500KG) = Max(F(1, 6), F(1, 1) + 500KG) = Max(400KG, 500KG) = 500KG

         F(2, 7) = Max(F(2-1, 7), F(2-1, 7-5) + 500KG) = Max(F(1, 7), F(1, 2) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 8) = Max(F(2-1, 8), F(2-1, 8-5) + 500KG) = Max(F(1, 8), F(1, 3) + 500KG) = Max(400KG, 500KG) = 500KG

         F(2, 9) = Max(F(2-1, 9), F(2-1, 9-5) + 500KG) = Max(F(1, 9), F(1, 4) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(F(1, 10), F(1, 5) + 500KG) = Max(400KG, 900KG) = 900KG

The subsequent calculation process will not be shown in detail. The results of calculation are as follows:

At this point, the last row and the last column are the optimal returns required. This is the bottom-up solution process of dynamic programming, which is translated into the code as follows:

/** * @param {Array<number>} p@param {Array<number>} p@param {Array<number>} p@param {Array<number>} */ function getBestColMiningV2(w:number,p:Array<number>, g:Array<number>):number { let resultArray = new Array(g.length+1); for (let index = 0; index < resultArray.length; index++) { resultArray[index] = new Array(w+1).fill(0) } for (let i = 1; i <= g.length; i++) { for (let j = 1; j <= w; j++) { if(j < p[i-1]) { resultArray[i][j] = resultArray[i - 1][j] } else { resultArray[i][j] = Math.max( resultArray[i -  1][j], resultArray[i - 1][j-p[i-1]] + g[i-1] ) } } } return resultArray[g.length][w] } console.log(getBestColMiningV2(10, [5,5,3,4,3], [400, 500, 200, 300, 350])Copy the code

stag3

The time and space complexity of the above bottom-up solution code is O(NW). This code has no optimization in time, but there are still some areas that can be optimized in space

The solution for the second line above:

         F(2, 1) = F(2-1, 1) = 0

         F(2, 2) = F(2-1, 2) = 0

         F(2, 3) = F(2-1, 3) = 0

        F(2, 4) = F(2-1, 4) = 0

         F(2, 5) = Max(F(2-1, 5), F(2-1, 5-5) + 500KG) = Max(F(1, 5), F(1, 0) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 6) = Max(F(2-1, 6), F(2-1, 6-5) + 500KG) = Max(F(1, 6), F(1, 1) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 7) = Max(F(2-1, 7), F(2-1, 7-5) + 500KG) = Max(F(1, 7), F(1, 2) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 8) = Max(F(2-1, 8), F(2-1, 8-5) + 500KG) = Max(F(1, 8), F(1, 3) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 9) = Max(F(2-1, 9), F(2-1, 9-5) + 500KG) = Max(F(1, 9), F(1, 4) + 500KG) = Max(400KG, 500KG) = 500KG

        F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(F(1, 10), F(1, 5) + 500KG) = Max(400KG, 900KG) = 900KG

You can see that the values in the second row are derived from the data in the first row,

For example, F(2, 10) = Max(F(2-1, 10), F(2-1, 10-5) + 500KG) = Max(400KG, 900KG) = 900KG

It follows from F(1, 10) and F(1, 5)

So we don’t need to save the whole table, but only save one row of data. When calculating the next row, we count from right to left (as can be seen from above) and replace the old data one by one with the following code:

function getBestColMiningV3(w:number,p:Array<number>, g:Array<number>):number { let resultArray = new Array(w + 1).fill(0); for (let i = 1; i <= g.length; i++) { for (let j = w; j >= 1; j--) { if(j >= p[i - 1]){ resultArray[j] = Math.max( resultArray[j], ResultArray [j -p [i-1]] + g[i-1])}} return resultArray[w]} console.log(getBestColMiningV3(10, [5,5,3,4,3], [400, 500, 200, 300, 350])Copy the code