Sự cố với vấn đề Project Euler 18

Question

Tôi hiện đang cố gắng giải quyết problem 18 of project Euler. Mục đích là:

Bằng cách bắt đầu ở phía trên cùng của tam giác dưới đây và di chuyển đến các số liền kề trên hàng dưới đây, tổng tối đa từ trên xuống dưới là 23.

 
     3 
    7 4 
    2 4 6 
    8 5 9 3 

Đó là, 3 + 7 + 4 + 9 = 23.

Tìm tổng tối đa từ trên xuống dưới của tam giác dưới đây:

 
       75 
       95 64 
       17 47 82 
       18 35 87 10 
      20 04 82 47 65 
      19 01 23 75 03 34 
      88 02 77 73 07 63 67 
      99 65 04 28 06 16 70 92 
     41 41 26 56 83 40 80 70 33 
     41 48 72 33 47 32 37 16 94 29 
     53 71 44 65 25 43 91 52 97 51 14 
     70 11 33 28 77 73 17 78 39 68 17 57 
    91 71 52 38 17 14 91 43 58 50 27 29 48 
    63 66 04 68 89 53 67 30 73 16 69 87 40 31 
    04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 

tôi đã cố gắng để giải quyết nó với các thuật toán sau đây:

public static void main(String[] args) throws NumberFormatException, IOException { 

     int[][] values = readFile(); 
     int depth = values.length - 2; 

     while (depth >= 0) { 
      for (int j = 0; j < depth; j++) { 
       values[depth][j] += Math.max(values[depth+1][j], values[depth+1][j+1]); 
      } 
      depth += -1; 
     } 

     values[0][0] += Math.max(values[1][0], values[1][1]); 

      System.out.println("The maximum path sum is: " + values[0][0]); 
    } 

Các giá trị mảng chứa tất cả các số từ hình tam giác nơi values[0][0] là yếu tố ở hàng đầu và values[n][n] là yếu tố cuối cùng trong hàng cuối cùng.

Thuật toán sử dụng cách tiếp cận nếu ví dụ tôi bắt đầu ở hàng cuối cùng và có lựa chọn giữa 04 + 63 và 62 + 63, tổng của trường trong đó 63 sẽ được đặt thành 125 vì đây là số tiền cao nhất. Thuật toán này hoạt động cho tam giác nhỏ, nhưng đối với tam giác lớn có vẻ như không thành công. Tôi không chắc chắn lý do tại sao và sẽ đánh giá cao mọi gợi ý.

Answer 1

Tôi tin rằng dòng:

for (int j = 0; j < depth; j++) { 

nên

for (int j = 0; j <= depth; j++) { 

vì ngay bây giờ bạn không ghé thăm yếu tố cuối cùng trên mỗi hàng. Tất nhiên, sau đó bạn không cần dòng

values[0][0] += Math.max(values[1][0], values[1][1]); 

vì nó đã được thực hiện trong vòng lặp.

Answer 2

Đây có thể không phải là giải pháp tốt nhất, nhưng điều gì sẽ xảy ra nếu cho mỗi lần lặp bạn theo dõi tổng số cho đến thời điểm đó. Sau đó, khi bạn đi đến hàng cuối cùng giá trị tối đa sẽ là câu trả lời của bạn.

Answer 3

Tôi không biết thuật toán chính xác, nhưng có bằng chứng dễ dàng về @Johns nhận xét về câu hỏi, rằng lựa chọn địa phương tốt nhất không nhất thiết dẫn đến giải pháp toàn cầu tốt nhất.

Xem xét việc này (cực đoan) ví dụ:

 
    1 
    1 0 
    1 0 1000 
1 0 0 0 
1 0 0 0 0 

Với thuật toán của bạn, bạn muốn rõ ràng là đi xuống rất trái của con đường và không bao giờ đọc 1000 rằng phải được trên con đường tốt nhất.