I have the following problem. Let's say I have a grid of values and that each point in this grid has two values associated with them. The numbers can be any positive number or 0. See figure 1. Now the challenge is to combine these grids so that each individual values has a sum of at least 3. That is, in the left upper corner: (1,4) can be combined with (6,1) to form (7,5), which is >3 for both values.
- Combinations with closeby cells are preferred
- But I they don't have to be connected
Could anybody help me solve this problem? What kind of approach could I possibly use if I want to (possibly approximately) maximize the amount of cells (ie. each combination should yield cells that don't have values much larger than 3 for each value) and minimize the "area" over which each combination is spread out. I.e., close by combinations are prefered. I realze that there is a trade of between these two aims.
If not a solution, could somebody point me in a direction on how to possibly solve this? Search-words, ideas, theories, similar porblems?
Code:
+---+---+---+---+
|1,4|5,5|1,1|4,5|
+---+---+---+---+
|6,1|0,0|2,2|2,2|
+---+---+---+---+
|5,4|5,5|1,1|0,0|
+---+---+---+---+
|0,1|5,5|6,7|2,5|
+---+---+---+---+
_one_ possible result:
Code:
+---+---+---+---+
| |5,5| 5,6 |
+7,5+---+---+---+
| | 4,4 |
+---+---+---+---+
| |5,5| 3,6|
+5,5+---+---+ +
| |5,5|6,7| |
+---+---+---+---+
Login
Register
FAQ
Search
