一道有意思的算法题

Question

前几天在CSDN上看人发帖问的，当时觉得很有意思就留下来了，现在找不到原帖，题意如下：
/*
 * 伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，
 * 为部落赢得了莫大荣誉。首领决定要重重奖赏，
 * 他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，
 * 南北向和东西向的道路纵横交错。
 * 现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。
 * 你可以沿着道路飞奔，拾取路口的娃娃，
 * 要求是任何时刻必须是一个套娃，装好后就不能再拆开了。
 * 注意不要走重复路。”
 * 请你为伊万洛夫规划路线，使得他能够有最大的收获。
 */我想了一天左右，最后是用tree模型去实现的，（偷懒用了swing里面的DefaultMutableTreeNode类）代码如下，作抛砖引玉之用，希望有高手可以提点更优的算法，感激！
import java.util.ArrayList;
import java.util.HashMap;
import javax.swing.tree.DefaultMutableTreeNode;public class MaxSum {
//nums代表由娃娃重量组成的二维数组，x,y代表初始入口坐标
public static void findMaxSum(int[][] nums,int x,int y){

//初始化树
if(x<0||x>nums.length||y<0||y>nums[x].length){
return;
}
int rootnumber=nums[x][y];
DefaultMutableTreeNode root = new DefaultMutableTreeNode(rootnumber);
addChild(root, nums, x, y);

//获得所有的叶节点
ArrayList list = new ArrayList();
findAllLeafs(list,root);

//遍历叶节点找出所有路径
ArrayList ways = new ArrayList();
for(Object leaf:list){
DefaultMutableTreeNode node = (DefaultMutableTreeNode) leaf;
StringBuffer way = new StringBuffer();
checkleaf(way,node);
ways.add(way.toString());
}
//对所有路径求和，找出最大值
HashMap map = new HashMap();
Integer maxSum = (Integer) root.getUserObject();
map.put(maxSum, new String[]{root.getUserObject().toString()});
for(int i =0;i<ways.size();i++){
int sum = 0;
String[] strs =((String) ways.get(i)).split(" ");
for(String str:strs){
sum+=Integer.parseInt(str);
}
map.put(sum, strs);
if(sum>maxSum){
maxSum=sum;
}
}
String[] maxWay = (String[]) map.get(maxSum);

//打印最优路径和最大获取量
System.out.println("路径为：");
for(int i = maxWay.length-1;i>=0;i--){
System.out.print(maxWay[i]);
if(i>0){
System.out.print("-->");
}
}
System.out.println();
System.out.println("最多可以拿到"+maxSum+"斤娃娃！");
}
//遍历某个叶节点-根节点的所有节点
public static void checkleaf(StringBuffer way,DefaultMutableTreeNode node ){
way.append(node.getUserObject());
way.append(" ");
Integer value = (Integer) node.getUserObject();
DefaultMutableTreeNode father = (DefaultMutableTreeNode) node.getParent();
if(father.isRoot()){
way.append(father.getUserObject());
way.append(" ");
Integer val = (Integer) father.getUserObject();
}else{
checkleaf(way,father);
}
}
//找出所有叶节点：
public static void findAllLeafs(ArrayList list,DefaultMutableTreeNode root){
for(int i =0;i<root.getChildCount();i++){
DefaultMutableTreeNode child = (DefaultMutableTreeNode) root.getChildAt(i);
if(child.isLeaf()){
list.add(child);
}else{
findAllLeafs(list,child);
}
}
}
//添加节点
public static void addChild(DefaultMutableTreeNode node,int[][] nums,int x,int y){
int nodenumber=(Integer) node.getUserObject();
if(y+1<nums[x].length&&nums[x][y+1]>nodenumber&&!isFather(node,nums[x][y+1])){
int childnumber = nums[x][y+1];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x,y+1);
}
if(y-1>=0&&nums[x][y-1]>nodenumber&&!isFather(node,nums[x][y-1])){
int childnumber = nums[x][y-1];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x,y-1);
}
if(x-1>=0&&nums[x-1][y]>nodenumber&&!isFather(node,nums[x-1][y])){
int childnumber = nums[x-1][y];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x-1,y);
}
if(x+1<nums.length&&nums[x+1][y]>nodenumber&&!isFather(node,nums[x+1][y])){
int childnumber = nums[x+1][y];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x+1,y);
}
}
//判断一个节点是不是另外一个节点的父节点
public static boolean isFather(DefaultMutableTreeNode child,int nodevalue){
DefaultMutableTreeNode father = (DefaultMutableTreeNode) child.getParent();
if(father ==null){
return false;
}
int value = (Integer) father.getUserObject();
if(value == nodevalue){
return true;
}else{
isFather(father,nodevalue);
}
return false;
}
public static void main(String[] args) {
int[][] nums = new int[][]{
{1,3,7,16,20},
{29,23,22,5,2},
{27,13,11,9,8},
{15,6,21,14,19}
};
int x =0;
int y =0;
findMaxSum(nums,x,y);
}
}输出结果如下：
路径为：
1-->3-->7-->22-->23-->29
最多可以拿到85斤娃娃！

Answer 1

修改了上面说的BUG，现在应该更接近正确答案了，方法、变量什么的命令都很不规范（:p,高手轻拍）
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import javax.swing.tree.DefaultMutableTreeNode;public class MaxSum {
//nums代表由娃娃重量组成的二维数组，x,y代表初始入口坐标
public static void findMaxSum(int[][] nums,int x,int y){

//初始化树
if(x<0||x>nums.length||y<0||y>nums[x].length){
return;
}
int rootnumber=nums[x][y];
DefaultMutableTreeNode root = new DefaultMutableTreeNode(rootnumber);
addChild(root, nums, x, y);

//获得所有的叶节点
ArrayList list = new ArrayList();
findAllLeafs(list,root);

//遍历叶节点找出所有路径
ArrayList ways = new ArrayList();
for(Object leaf:list){
DefaultMutableTreeNode node = (DefaultMutableTreeNode) leaf;
StringBuffer waysb = new StringBuffer();
checkleaf(waysb,node);
String[] way = waysb.toString().split(" ");
List ls = Arrays.asList(way);
Collections.reverse(ls);
ways.add(ls);
}

int maxSum = 0;
HashMap eachWay = new HashMap();
HashMap maxWays=new HashMap(); 
for(Object obj:ways){
List way = (List) obj;
Object[] objs= maxSum(way,0);
int max = (Integer)objs[0];
List maxWay = (List) objs[1];
if(max>maxSum){
maxSum=max;
maxWays.put(max, maxWay);
eachWay.put(max, way);
}
}
System.out.print("最优路径：");
System.out.println(eachWay.get(maxSum));
System.out.print("要拿的娃娃为：");
System.out.println(maxWays.get(maxSum));
System.out.println("最多可以拿"+maxSum+"斤娃娃！"); }
//遍历某个叶节点-根节点的所有节点
public static void checkleaf(StringBuffer way,DefaultMutableTreeNode node ){
way.append(node.getUserObject());
way.append(" ");
DefaultMutableTreeNode father = (DefaultMutableTreeNode) node.getParent();
if(father.isRoot()){
way.append(father.getUserObject());
way.append(" ");
}else{
checkleaf(way,father);
}
}
//找出所有叶节点：
public static void findAllLeafs(ArrayList list,DefaultMutableTreeNode root){
for(int i =0;i<root.getChildCount();i++){
DefaultMutableTreeNode child = (DefaultMutableTreeNode) root.getChildAt(i);
if(child.isLeaf()){
list.add(child);
}else{
findAllLeafs(list,child);
}
}
}
//添加节点
public static void addChild(DefaultMutableTreeNode node,int[][] nums,int x,int y){
if(y+1<nums[x].length&&!isFather(node,nums[x][y+1])){
int childnumber = nums[x][y+1];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x,y+1);
}
if(y-1>=0&&!isFather(node,nums[x][y-1])){
int childnumber = nums[x][y-1];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x,y-1);
}
if(x-1>=0&&!isFather(node,nums[x-1][y])){
int childnumber = nums[x-1][y];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x-1,y);
}
if(x+1<nums.length&&!isFather(node,nums[x+1][y])){
int childnumber = nums[x+1][y];
DefaultMutableTreeNode child = new DefaultMutableTreeNode(childnumber);
node.add(child);
addChild(child,nums,x+1,y);
}
}
//判断一个节点是不是另外一个节点的父节点
public static boolean isFather(DefaultMutableTreeNode child,int nodevalue){
boolean flag = false;
DefaultMutableTreeNode father = (DefaultMutableTreeNode) child.getParent();
if(null !=father){
int value = (Integer) father.getUserObject();
if(value==nodevalue){
flag = true;
}else{
flag = isFather(father,nodevalue);
}
}
return flag;
}

/*
 * 对于每一条可走的路径选出可以拿到的最大的和
 * 题目转化为在一个list中按顺序找出最大的和
 */
public static Object[] maxSum(List list,int beginIndex){
DefaultMutableTreeNode root = new DefaultMutableTreeNode(list.get(beginIndex));
addChildren(root,list,beginIndex+1);
ArrayList leaflist = new ArrayList();
findAllLeafs(leaflist,root);
ArrayList ways = new ArrayList();
for(Object leaf:leaflist){
DefaultMutableTreeNode node = (DefaultMutableTreeNode) leaf;
StringBuffer waysb = new StringBuffer();
checkleaf(waysb,node);
String[] way = waysb.toString().split(" ");
List ls = Arrays.asList(way);
Collections.reverse(ls);
ways.add(ls);
}
//对所有路径求和
HashMap wayMap = new HashMap();
Integer maxSum =0;
for(Object obj:ways){
Integer sum =0;
List waylist = (List) obj;
for(Object obj1:waylist){
sum+=(Integer.parseInt((String)obj1));
}
wayMap.put(sum, obj);
if(sum>maxSum){
maxSum=sum;
}
}
//找出最优路径：
Object[] objs = new Object[2];
List maxWay = (List) wayMap.get(maxSum);
objs[0]=maxSum;
objs[1]=maxWay;
return objs;

}
//在list中往根节点添加子节点（子节点值大于父节点值）
public static void addChildren(DefaultMutableTreeNode root,List list,int index){
if(index>=list.size()){
return;
}else{
for(int i = index;i<list.size();i++){
if(((Integer.parseInt((String) list.get(i))>(Integer.parseInt((String) root.getUserObject()))))){
DefaultMutableTreeNode children = new DefaultMutableTreeNode(list.get(i));
root.add(children);
addChildren(children,list,i+1);
}
}
}
}
public static void main(String[] args) {
int[][] nums = new int[][]{
{1,3,7,16,20},
{29,23,22,5,2},
{27,13,11,9,8},
{15,6,21,30,19}
};
int x =0;
int y =0;
findMaxSum(nums,x,y);
}
}
输出结果：
最优路径：[1, 3, 7, 16, 20, 2, 5, 9, 8, 19, 30, 21, 11, 22, 23, 13, 27, 29]
要拿的娃娃为：[1, 3, 7, 16, 20, 21, 22, 23, 27, 29]
最多可以拿169斤娃娃！

Answer 2

典型的DP问题，
MAX(NodeX)=NodeX.value + max{MAX value of all next nodes}

Answer 3

sorry ，理解有误。还是DP算法，但会有些复杂

Answer 4

这是原题,其中要考虑0的情况,比没有0时难多了伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”
请你为伊万洛夫规划路线，使得他能够有最大的收获。
Input:  cross.txt
        输入包括多组测试用例；
        每个测试用例开始是一对整数<R, C>，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数（或0）W[r,c]，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或表示没有放置娃娃）。
Output:
        输出能有最大收获的路径规划。