Miner Board - DP

Question

Given checkers with four rows and columns N each cell in the matrix matters. When using 2N tokens, which should be placed on the board (each in one cell), therefore, the total amount of all values ​​in the matrix cells will be as large as possible (maximum value).

The limit of marker placement is that two tokens cannot be horizontally or vertically adjacent to each other.

You do not need to post all 2N tags.

There are eight legal ways to place tokens in a column. Therefore, I define 8 arrays with size N when each of them describes a parameter.

In any case, using dynamic programming, I need to build a recursive equation for the problem.

I figured it out:

 A(i,j) = max { A(i,j) , A(i,j) + max { A(i-1,j-1) , ... , H(i-1,j-1) } } , B(i,j) = .... , H(i,j) = ... 

When A is the first array and H is the 8th array.

Now I don’t think my recursive equation is good. And even if this is so, I have no idea how to add conditions (two tokens cannot be horizontally or vertically adjacent to each other) with a recursive equation.

Can anybody help?

Answer 1

This answer is virtually the same as unkulunkulu, although independently obtained. I include it here because it may be notationally better or a little easier to process arrays.

Next, let p or q in {0..7} be the indices of one of the eight configurations, and k the column index. Let V(k,p) be the value of the configuration p in column k . Let W(k,p) be the value of the best column configuration 0..k , which ends with the configuration p in column k . Let φ(p,q) be equal to 1 if the configurations p,q allowed side by side, otherwise 0. ( φ equivalent to the unkulunkulu incidence matrix.) The symbol ∞ represents a number greater than the sum of the values ​​of the positive cell of the matrix.

Then W (k + 1, p) = V (k + 1, p) + max _{q∈ {0..7}} (W (k, q) · φ (p, q) + ∞ · (φ (p, q) -1))
when k≥0 and W (0, p) = V (0, p).

Answer 2

That's right, you have 8 possible ways to place tokens in a column:

 ABCDEFGH e * * * m * * p * * t * * * y 

Now you can only have specific columns following other columns. For instance:

• A can be a neighbor on any column,
• Only A can be a neighbor to himself,
• B may be a neighbor to C and G , but may not be adjacent to another B or F or H ,
• H can only be a neighbor to A , C or D , etc.

It should be noted that A can be useful if this column is in contact with F and G

So, we have a (non-oriented) graph:

  ABCDEFGH A + + + + + + + + B + - + + + - + - C + + - + + + - + D + + + - + - + + E + + + + - + - - F + - + + + - + - G + + - + - + - - H + - + + - - - - 

The incident matrix is ​​presented above.

After that, we define A(i) as the maximum possible amount that we can get from the first columns of i if column i th finished placing the marker of type A The same goes for B , C , ..., H

Then you have a recursive formula:

 X(i+1) = {max Y(i) where X and Y can be neighboring columns} + {sum of the cells in the i+1 column for placement X} 

here X runs through all possible placements A , B , C , ..., H

The initial values ​​are A(0) = 0, B(0) = 0, ..., H(0) = 0 .

The final answer is max{ A(N), B(N), C(N), D(N), ..., H(N) } .

Note:

The above solution or idea, implementation may be different. For example, you can hard-code everything (provided that Board[i][j] is the value placed on the board, the indices start at 0 ):

 F(i+1) = max{ A(i), C(i), E(i), G(i) } + // This is from the matrix above Board[0][i+1] + Board[2][i+1] // This is from the definition of F type column 

And similarly for each letter. You do not have to have an incidence matrix as a real entity in the program, just keep this in mind when building expressions.