各位大哥大姐，能不能帮我看看这一道简单的c语言题目。

显示全部楼层 · 2010-8-17 19:59:37

输入一个N*N的二维数组，所有的元素都是自然数从中取任意个数，使得任意两个数都不相邻（包括行和列），并且取出的所有数的和最大，
输出最大值。
例如输入
751521
751528
34705
则输出
188
最好不要回答代码，把算法说明白就可以了
谢谢啦
我可能没有说明白，输入的有可能是这样的
7511
1 175
751 1
这样的话，分成的两部分和都不是最大的
就是说不能简单的分成两部分，
取的个数最多的组合和并不一定越大。

千问 · 2010-8-17 19:59:37

都是自然数的话那么就都是大于0的我们要取出的和最大那么在可行条件下取得越多越好那可行条件就是如果我取（1,1）这个75那么我还可以取的是（1,3）21，（2,2）15，（3,1）34，（3,3）5如果我不取（1,1）我取（1,2）15那么我还可以取的就是（2,1）75，（2,3）28，（3，2）70也就是说我可以把矩阵分成两部分看其中哪部分的和更大我就取那部分 -----------------------------------应该是我理解错楼主的意思了按你补充的说法这道题就要用到dp的思想（动态规划）首先是肯定不能贪心的，也就是一直选最大的1 1 11 1 751

千问 · 2010-8-17 19:59:37

可以用深搜做，遍历每个位置，如a[j]，则与其不相邻的点为a[i-1][j-1],a[i-1][j+1],a[i+1][j-1],a[i+1][j+1]共4个点，将其加入队列