日期:2014-05-20  浏览次数:20744 次

一道算法题、!
int number[5][5]={22,32,14,77,45,0,12,34,37,23,0,0,44,23,15,0,0,0,34,54,0,0,0,0,88};
排列方式如下、

从最左上角开始往右或往右下走,所经过的值总和最大,求出总值和经过的那条的线路,用java实现


------解决方案--------------------
java淡忘了
------解决方案--------------------
有个问题,能往下吗?如果不能往下,那么只有从开始就直接往右下了,否则怎么能到终点?
如果只是5*5的数组的话,可以考虑全排,找出最大的。
------解决方案--------------------
这也属于动态规划吧。
------解决方案--------------------
简单写了段代码,通过递归取所有可能路径,然后排序取出和最大的一条路径
Java code

import java.util.*;
public class Test {    
    static class DataNode { //定义一个类用于记录数组元素的位置的值
        int x, y, value;
        public DataNode(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

    static class DataList implements Comparable<DataList> { //定义一个类用于记录路径
        int sum = 0;
        List<DataNode> nodes = new ArrayList<DataNode>();

        public DataList() {}
        public void addNode(DataNode node) {
            nodes.add(0, node);
            sum += node.value;
        }
        public int compareTo(DataList dl) {
            return dl.sum - sum;
        }
    }

    public static void main(String[] args) throws Throwable {
        int[][] number={
            {22,32,14,77,45},
            {0,12,34,37,23},
            {0,0,44,23,15},
            {0,0,0,34,54},
            {0,0,0,0,88}};

        List<DataList> result = findAll(number, 0, 0); //获取所有路径
        if (result.size() > 0) {
            Collections.sort(result); //降序排序所有路径
            //for (DataList dl : result) {
            DataList dl = result.get(0); //取出第一条路径(该路径权值最大)
                System.out.printf("sum=%d\n", dl.sum);
                for (DataNode n : dl.nodes) {
                    System.out.printf("(%d,%d:%d), ", n.x, n.y, n.value);
                }
                System.out.println();
            //}
        }
    }

    //定义一个递归寻找所有路径的方法
    public static List<DataList> findAll(int[][] number, int x, int y) {
        if (number==null || number.length==0 || number[0].length==0) {
            return new ArrayList<DataList>(); //非法数据的时候返回0元素的集合
        }

        List<DataList> result = new ArrayList<DataList>();
        if (x==number.length-1 && y==number[0].length-1) { //路径走到终点的时候递归结束
            DataList dl = new DataList();
            dl.addNode(new DataNode(x, y, number[x][y]));
            result.add(dl);
            return result;
        }

        if (x < number.length && y < number[0].length) { //右下有效时递归取右下路径集合
            List<DataList> tmp = findAll(number, x+1, y+1);
            for (DataList dl : tmp) { //在递归获取的子集合中追加当前元素
                dl.addNode(new DataNode(x, y, number[x][y])); 
            }
            result.addAll(tmp); //把右下方的子集合路径追加到最终的结果集中
        }
        if (y < number[0].length) { //右方有效时递归取右方路径集合
            List<DataList> tmp = findAll(number, x, y+1);
            for (DataList dl : tmp) { //同上
                dl.addNode(new DataNode(x, y, number[x][y]));
            }
            result.addAll(tmp);
        }
        if (x < number.length) { //下方有效时递归取下方有效集合
            List<DataList> tmp = findAll(number, x+1, y);
            for (DataList dl : tmp) { //同上
                dl.addNode(new DataNode(x, y, number[x][y]));
            }
            result.addAll(tmp);
        }
        return result;
    }
}

------解决方案--------------------
数可以为负数没