kết quả từ 1 tới 9 trên 9

Ai giúp mình bài quy hoạch động này với!!!

  1. #1
    Ðến Từ
    Bình Định
    Thành Viên Thứ: 333496
    Giới tính: Nam
    Bài gửi
    26

    Ai giúp mình bài quy hoạch động này với!!!

    Cho một bảng A kích thước m x n (1 <= m, n <= 100), trên đó ghi các số nguyên aij (|aij| <= 100). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được).
    Input

    Dòng 1: Ghi hai số m, n là số hàng và số cột của bảng.M dòng tiếp theo, dòng thứ i ghi đủ n số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
    Output

    Gồm 1 dòng duy nhất ghi tổng lớn nhất tìm được

    Example

    Input:
    5 7
    9 -2 6 2 1 3 4
    0 -1 6 7 1 3 3
    8 -2 8 2 5 3 2
    1 -1 6 2 1 6 1
    7 -2 6 2 1 3 7
    Output:
    41

    Em có làm bài đó như sau mà nó ra có 39 à! Mong mọi người giúp đỡ e ạ
    Mã:
    uses crt;
    var  m,n,i,j:integer;
    a,f:array[0..100,0..100] of integer;
    procedure input;
    var  f:text;
    begin
            assign(f,'d:\pascal\dgdidai1\input.txt');
            reset(f);
            readln(f,n,m);
            for i:=1 to n do
            begin
                    for j:=1 to m do
                    read(f,a[i,j]);
            readln(f);
            end;
    end;
    function max(a,b:integer):integer;
    begin
            if a>b then exit(a) else exit(b);
    end;
    procedure qhd;
    begin
            fillchar(f,sizeof(f),0);
            for i:=1 to n do
            for j:=1 to m do
            f[i,j]:= max(f[i-1,j-1],max(f[i,j-1],f[i+1,j-1]))+a[i,j];
    end;
    procedure rslt;
    var kq:integer;
    begin   kq:=-maxint;
            for i:=1 to n do
            if f[i,m]>kq then kq:=f[i,m];
            write(kq);
    end;
    begin
    clrscr;
            input;
            qhd;
            rslt;
    readln;
    end.
    Quick reply to this message Trả lời       

  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trong procedue qhd, bạn thử đổi thứ tự của 2 dòng loop i và j lại nhé. Bởi vì điền giá trị cho f[i,j] là theo cột, cho nên phải duyệt từng hàng i cho mỗi cột j. Ngoài ra, bạn nên tăng giá trị lên 101, chứ ko phải 100.

    Cải tiến thêm: cột j của mảng f chỉ phụ thuộc vào cột j-1 của nó và giá trị a[i,j] mà thôi. Như vậy, thay vì lưu mảng f 100 x 100, chúng ta chỉ cần 1 mảng m dòng 2 cột rồi đổi qua đổi lại. Cách làm này sẽ đỡ hao bộ nhớ hơn (thay vì lưu 1 mảng 10000 phần từ thì chỉ cần lưu 1 mảng 200 phần tử).

    Mã:
    begin
            fillchar(f,sizeof(f),0);
            t := 0;
            for j:=1 to m do
                 begin
                      for i:=1 to n do
                           f[i,t]:= max(f[i-1,1-t],max(f[i,1-t],f[i+1,1-t]))+a[i,j];
                      t:= 1-t;
                 end;
    end;
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. 2 thành viên đã cảm ơn tengiday:


  4. #3
    Ðến Từ
    Yên Bái
    Thành Viên Thứ: 235356
    Giới tính: Nam
    Bài gửi
    746

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    đọc 1 hồi mới hiểu đề dc
    tổng lớn nhất sẽ = max của mỗi cột + lại với nhau
    cầy xây dụng hàm tính max cho mỗi cột rồi lấy tổng thôi
    class TapLamHacker{ private String TráiTim;
    private void Set_TráiTim(String Gái){ this.TráiTim = "Thanh Trâm"; }
    public String Get_TráiTim(){ return "Thanh Trâm"; }
    public String ToString(){return"My love is Thanh Trâm For one future go shopping not concerned about price ";}
    } Liên hệ Skype: Taplamhacker

  5. Đã cảm ơn taplamhacker:


  6. #4
    Ðến Từ
    Bình Định
    Thành Viên Thứ: 333496
    Giới tính: Nam
    Bài gửi
    26

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi tengiday Xem bài viết
    Trong procedue qhd, bạn thử đổi thứ tự của 2 dòng loop i và j lại nhé. Bởi vì điền giá trị cho f[i,j] là theo cột, cho nên phải duyệt từng hàng i cho mỗi cột j. Ngoài ra, bạn nên tăng giá trị lên 101, chứ ko phải 100.

    Cải tiến thêm: cột j của mảng f chỉ phụ thuộc vào cột j-1 của nó và giá trị a[i,j] mà thôi. Như vậy, thay vì lưu mảng f 100 x 100, chúng ta chỉ cần 1 mảng m dòng 2 cột rồi đổi qua đổi lại. Cách làm này sẽ đỡ hao bộ nhớ hơn (thay vì lưu 1 mảng 10000 phần từ thì chỉ cần lưu 1 mảng 200 phần tử).

    Mã:
    begin
            fillchar(f,sizeof(f),0);
            t := 0;
            for j:=1 to m do
                 begin
                      for i:=1 to n do
                           f[i,t]:= max(f[i-1,1-t],max(f[i,1-t],f[i+1,1-t]))+a[i,j];
                      t:= 1-t;
                 end;
    end;
    Cảm ơn bạn nhìu nha...Mình đổi vị trí i với j thì được nhưng lại không hiểu tại sao lại phải đổi...đó h mình làm mảng 2 chìu thì chỉ viết như vậy thôi

  7. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi Richard Annowit Xem bài viết
    Cảm ơn bạn nhìu nha...Mình đổi vị trí i với j thì được nhưng lại không hiểu tại sao lại phải đổi...đó h mình làm mảng 2 chìu thì chỉ viết như vậy thôi
    Khi chúng ta viết như thế này
    Mã:
    for i:=1 to m do
       for j:=1 to n do
          a[i,j] ....
    tức có nghĩa là đang duyệt mảng theo từng dòng từ trên xuống dưới, mỗi dòng từ trái sang phải.
    Khi chúng ta viết như thế này
    Mã:
    for j:=1 to n do
       for i:=1 to m do
          a[i,j] ...
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.

  8. 2 thành viên đã cảm ơn tengiday:


  9. #6
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 146858
    Giới tính: Nam
    Bài gửi
    7.537

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi tengiday Xem bài viết
    Khi chúng ta viết như thế này
    Mã:
    for i:=1 to m do
       for j:=1 to n do
          a[i,j] ....
    tức có nghĩa là đang duyệt mảng theo từng dòng từ trên xuống dưới, mỗi dòng từ trái sang phải.
    Khi chúng ta viết như thế này
    Mã:
    for j:=1 to n do
       for i:=1 to m do
          a[i,j] ...
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.
    Sao bác tengiday giỏi thế, biết cả phần mềm, phần cứng kèm theo lập trình cũng rành nữa
    Hãy nhấn nút Thank nếu thấy bài viết hữu ích
    Bộ sưu tập cực khủng

  10. 2 thành viên đã cảm ơn quanltv:


  11. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi quanltv Xem bài viết
    Sao bác tengiday giỏi thế, biết cả phần mềm, phần cứng kèm theo lập trình cũng rành nữa
    Cám ơn bạn nhiều; thật ra mình ko có biết sâu như nhiều bạn trên 4rum. Mình biết sơ sơ để tự sửa cho mình vì bên này tiền dịch vụ đắt quá.

  12. Đã cảm ơn tengiday:


  13. #8
    Ðến Từ
    Bình Định
    Thành Viên Thứ: 333496
    Giới tính: Nam
    Bài gửi
    26

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi tengiday Xem bài viết
    Khi chúng ta viết như thế này
    Mã:
    for i:=1 to m do
       for j:=1 to n do
          a[i,j] ....
    tức có nghĩa là đang duyệt mảng theo từng dòng từ trên xuống dưới, mỗi dòng từ trái sang phải.
    Khi chúng ta viết như thế này
    Mã:
    for j:=1 to n do
       for i:=1 to m do
          a[i,j] ...
    tức có nghĩa là đang duyệt mảng theo từng cột từ trái sang phải, mỗi cột từ trên xuống dưới.
    Vì yêu cầu của bài toán: đi từ cột trái sang cột phải, nên phải duyệt mảng theo cột (phải có giá trị của cột thứ j rồi mới đi tiếp sang cột j+1). Bạn chạy theo vòng loop ghi rõ giá trị của i và j ra sẽ thấy rõ hơn.
    À...mình hiểu rồi..mà bạn ơi...Bạn có tài liệu quy hoạch động nào hay không hay là rèn luyện tư duy j đó cho mình xin với

  14. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Ai giúp mình bài quy hoạch động này với!!!

    Trích Nguyên văn bởi Richard Annowit Xem bài viết
    À...mình hiểu rồi..mà bạn ơi...Bạn có tài liệu quy hoạch động nào hay không hay là rèn luyện tư duy j đó cho mình xin với
    Cái này thì mình ko có; mình học QHD đã 6-7 năm về trước rồi. Mình nghĩ có thể tìm trên mạng nhiều bài tập QHD tương tự (Google ra rất nhiều).
    Nếu bạn muốn đọc tài liệu tiếng Anh thì có thể search cụm từ dynamic programming.

  15. Đã cảm ơn tengiday: