java - 为最大硬币收集添加回溯算法？

Question

我有这个伪代码用于回溯以找到从单元格(6,6)向后的路径。

If F[i − 1, j] > F[i, j − 1] then the path to (i, j) came from above. If F[i − 1, j] < F[i, j − 1] then the path to (i, j) came from the left. If F[i − 1, j] = F[i, j − 1] then either direction works"

我不确定如何修改我的代码来执行此操作，但我确信它位于 ** ** 代码之间，我希望它打印出代码遍历的路径的索引，例如输出应该打印类似 (6,6)(5,6)(4,6)(4,5)(4,4)(3,4)(3,3)(2,3)(1 ,3)(1,2)(1,1)

import java.util.Random;
public class project {
private static int max(int i, int j) {
    return i > j ? i : j;
}
public static int collect(int[][] board) {

    int rowLen = board.length;
    int columnLen = board[0].length;
    int[][] F = new int[rowLen][columnLen];
    F[0][0] = (int) board[0][0];


    for (int column = 1; column < columnLen; column++) {
        F[0][column] = (int)(F[0][column - 1] + board[0][column]);
    }

    **for (int row = 1; row < rowLen; row++) {
        F[row][0] = (int)(F[row - 1][0] + board[row][0]);
        for (int column = 1; column < columnLen; column++) {
            F[row][column] = (int)(max(F[row - 1][column],
                F[row][column - 1]) + board[row][column]);**
        }  
    }   

    System.out.println("-------------------------------------------");
    System.out.println("maxpath board");
    for (int row = 0; row < 6; row++) {
        for (int column = 0; column < 6; column++) {
            System.out.print(F[row][column] + "  ");
        }
        System.out.println();

    }

    return F[rowLen - 1][columnLen - 1];
}
public static void main(String[] args) {
    //create the grid
    final int rowWidth = 6;
    final int colHeight = 6;
    final int[] coinvalues = {
        0,
        1
    };
    Random rand = new Random();
    int[][] board = new int[rowWidth][colHeight];
    for (int[] board1: board) {
        for (int col = 0; col < board1.length; col++) {
            board1[col] = coinvalues[rand.nextInt(coinvalues.length)];
        }
    }System.out.println("coinboard");
    //display output
    for (int[] board1: board) {
        for (int j = 0; j < board1.length; j++) {
            System.out.print(board1[j] + " ");
            //System.out.println();
        }
        System.out.println();
    }
    System.out.println("Maximum Coins : " + collect(board));

}
}
sample output- coinboard
1 0 1 1 1 0 
0 0 1 0 0 0 
0 0 1 0 1 0 
1 0 1 0 1 1 
0 1 0 1 0 1 
1 1 1 1 0 1 
-------------------------------------------
maxpath board
1  1  2  3  4  4  
1  1  3  3  4  4  
1  1  4  4  5  5  
2  2  5  5  6  7  
2  3  5  6  6  8  
3  4  6  7  7  9


Maximum Coins : 9

Answer 1

这是我对您执行任务的问题的编辑(顺便说一句，当两者给出相同的利润时，我的代码在回溯中总是优先考虑向上移动而不是向左移动)-

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.Random;
class project {
private static int max(int i, int j) {
    return i > j ? i : j;
}
public static void paste(int i,int j){
    System.out.println("("+i+","+j+")");
}
public static int collect(int[][] board) {

    int rowLen = board.length;
    int columnLen = board[0].length;
    int[][] F = new int[rowLen][columnLen];
    F[0][0] = (int) board[0][0];


    for (int column = 1; column < columnLen; column++) {
        F[0][column] = (int)(F[0][column - 1] + board[0][column]);
    }

    for (int row = 1; row < rowLen; row++) {
        F[row][0] = (int)(F[row - 1][0] + board[row][0]);
        for (int column = 1; column < columnLen; column++) {
            F[row][column] = (int)(max(F[row - 1][column],
                F[row][column - 1]) + board[row][column]);
        }  
    }   

    System.out.println("-------------------------------------------");
    System.out.println("maxpath board");
    for (int row = 0; row < 6; row++) {
        for (int column = 0; column < 6; column++) {
            System.out.print(F[row][column] + "  ");
        }
        System.out.println();

}
int curr=F[rowLen - 1][columnLen - 1];
int i=rowLen-1;
int j=columnLen-1;
paste(i+1,j+1);
while(i>0&&j>0){

    if(i>0&&F[i-1][j]==curr){
        i=i-1;
    }
    else if(j>0&&F[i][j-1]==curr){
        j=j-1;
    }
    else if(i>0&&F[i-1][j]==curr-1){    
        i=i-1;
        curr--;
        paste(i+1,j+1);
    }
    else if(j>0&&F[i][j-1]==curr-1){    
        j=j-1;
        curr--;
        paste(i+1,j+1);
    }

}
    return F[rowLen - 1][columnLen - 1];
}
public static void main(String[] args) {
    //create the grid
    final int rowWidth = 6;
    final int colHeight = 6;
    final int[] coinvalues = {
        0,
        1
    };
    Random rand = new Random();
    int[][] board = new int[rowWidth][colHeight];
    for (int[] board1: board) {
        for (int col = 0; col < board1.length; col++) {
            board1[col] = coinvalues[rand.nextInt(coinvalues.length)];
        }
    }System.out.println("coinboard");
    //display output
    for (int[] board1: board) {
        for (int j = 0; j < board1.length; j++) {
            System.out.print(board1[j] + " ");
            //System.out.println();
        }
        System.out.println();
    }
    System.out.println("Maximum Coins : " + collect(board));

}
}