都市摩天楼问题

winxos

这是NOKIA手机上的一款游戏，电脑上有相应的版本。应该有很多人玩过这个游戏。
游戏规则：在一块固定大小的区域中建立房子，房子有blue,red,green,yellow四种颜色，
blue可以建立在任何地方，后面的颜色一定要建立在与前面所有的颜色相邻的地方，
比如说green需要建立在与blue,red都相邻的地段，
已经建好的房子可以覆盖，这就意思着应该考虑用一些房子做铺垫，
颜色越靠后的住的人越多，如何使固定城市人口最大化？
我将这个问题数学处理一下，转换为：
将1-4五个数填入指定区域，在填入的时候一定要满足大的数填在与所有比他小的数都相邻的地方，
填的数可以覆盖，问如何使的这块区域数的和最大？

比如说如果地图是2x2的区域可以如下：
00      
00
----------
00
11
----------
02
11
---------
32
13
--------
和为9，（这是我想到的最大的和）。
现在我们将问题简单化一些，
如何将n*n矩形区域和最大化？请制定一套和最大化规则，编程实现。
扩展问题：
随机制定地图，如何最大化？
如果填入的数是1-5又如何处理？

kon3155

楼主给的例子有问题吧，2*2的，是不可能有价值为3的房子的，3的周围要求有0，1，2呢！
最多只能是

02
21

kon3155

其实楼主对这个游戏的抽象不够准确，
如果要是求和最大的话，那么房子的价值不应该是0，1，2，3，房子的价值至少应该是1，3，8，20这样的比例才行。因为如果是0，1，2，3的话，那么就存在1+2=3+0的情况，其实1+2<3+0 的。还有不少用1，2，3，4来抽象的，那么就会存在2+3=1+4的情况，而其实2+3<4+1.

尽可能多盖最大价值（此例中为3）的房子本应该是玩这个游戏的一个技巧，如果0+3的组合和1+2的组合的价值是一样的话，那么尽可能多建价值为3的房子就不适用了（占同样的地方可以建1和2来代替3和0）

总之，要以每个房子能装的最大人口数来算他的价值才行，不能简单的把价值定为0，1，2，3，不然求和的最大值的时候会出现多种组合形式。

winxos

原帖由 kon3155 于 2009-3-9 09:35 发表
楼主给的例子有问题吧，2*2的，是不可能有价值为3的房子的，3的周围要求有0，1，2呢！
最多只能是

02
21

没有0，最小价值的房子是1，0代表没有任何建筑
13
32

winxos

原帖由 kon3155 于 2009-3-9 10:10 发表
其实楼主对这个游戏的抽象不够准确，
如果要是求和最大的话，那么房子的价值不应该是0，1，2，3，房子的价值至少应该是1，3，8，20这样的比例才行。因为如果是0，1，2，3的话，那么就存在1+2=3+0的情况，其实1+2

实际情况就是这样的，
1+4=2+3
最大值不一定就只有一种解。
在游戏中实际上1，2，3，4代表了10层楼，20层楼，30层楼，40层楼。
昨天晚上睡觉前想了下3*3的，我想到的最大情况是
243
414
342
总和=27

kon3155

原帖由 winxos 于 2009-3-10 11:58 发表

实际情况就是这样的，
1+4=2+3
最大值不一定就只有一种解。
在游戏中实际上1，2，3，4代表了10层楼，20层楼，30层楼，40层楼。

最后求的是最大人口数，又不是最大楼层数，10层楼可以住180人，20层楼可以住700人，30层楼可以住1500人，40层楼可以住2500人（这是我游戏里的最好成绩）。所以1+4>2+3！

winxos

原帖由 kon3155 于 2009-3-10 12:12 发表


最后求的是最大人口数，又不是最大楼层数，10层楼可以住180人，20层楼可以住700人，30层楼可以住1500人，40层楼可以住2500人（这是我游戏里的最好成绩）。所以1+4>2+3！

呵呵，你的这些数据肯定不是全PERFECT的楼层，
我10层最好打到了488人，29层788人，不过我的数据是电脑上那个版本的游戏，不是手机上的游戏，
就是因为不同的人可能达到最大层不一样，完美的高层楼是很难建造的，
所以我将问题考虑成1层楼面积是一样的，所以假定每层住的人一样，也算是将问题定一个标准，
所以到底1+4>2+3还是1+4=2+3
这不是我想解决的问题，
我主要是想希望大家能一起想一下楼的排布问题，如何使得楼层数最多。

kon3155

5*5 盖房子过程

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

1 2 2 2 1
1 1 1 1 1
2 1 1 1 2
1 1 1 1 1
1 2 2 2 1

3 2 2 2 3
1 1 1 1 1
2 1 1 1 2
1 1 1 1 1
3 2 2 2 3

3 4 2 4 3
4 1 1 1 4
2 1 1 1 2
4 1 1 1 4
3 4 2 4 3

3 4 2 4 3
4 1 2 1 4
2 1 1 1 2
4 1 2 1 4
3 4 2 4 3

3 4 2 4 3
4 3 2 3 4
2 1 1 1 2
4 3 2 3 4
3 4 2 4 3

3 4 2 4 3
4 3 4 3 4
2 4 1 4 2
4 3 4 3 4
3 4 2 4 3

winxos

原帖由 kon3155 于 2009-3-11 13:15 发表
5*5 盖房子过程

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

1 2 2 2 1
1 1 1 1 1
2 1 1 1 2
1 1 1 1 1
1 2 2 2 1

3 2 2 2 3
1 1 1 1 1
2 1 1 1 2
1 1 1 1 1
3 2 2 2 3

3 4 2 4 3
...

how you get such result?can you solve more bigger maps?

kon3155

原帖由 winxos 于 2009-3-12 16:56 发表

how you get such result?can you solve more bigger maps?

我是倒着推的，让每个位置都最大化
首先四个角最大只能是3，然后和3相邻的最大是4，两个4之间最大只能是2，这样最外边一圈就填完了，剩下的就是里面一个3*3的了，还是同样的每个位置最大化，就得到了理论上最后的结果了！
3 4 2 4 3
4 3 4 3 4
2 4 1 4 2
4 3 4 3 4
3 4 2 4 3
然后再看怎么覆盖才能达到就可以了！
这个方法7*7或是9*9 可能不太适用，楼主自己试试看吧。