Trang 1/2 12 cuối
kết quả từ 1 tới 12 trên 13

Giải giúp mình bài này bằng Quy Hoạch Động 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

    Giải giúp mình bài này bằng Quy Hoạch Động với

    Bờm thắng phú ông trong một cuộc đánh cược và buộc phú ông phải đãi rượu. Phú ông bèn bày ra một dãy n chai chứa đầy rượu và nói với bờm rằng có thể uống bao nhiêu tùy ý, nhưng đã chọn chai nào thì uống hết và không được uống ở 3 chai liền nhau bởi đó là điều xui xẻo. Hãy chỉ cho Bờm cách uống được nhiều rượu nhất.
    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: Giải giúp mình bài này bằng Quy Hoạch Động với

    Thật ra bài này ko cần tới QHĐ, nhưng nếu muốn thì bạn có thể thử cách sau:
    F[i] = số lượng chai rượu tối đa Bờm uống đc nếu uống chai thứ i.
    Như vậy,
    Mã:
    F[i] = max (F[i - 2] + 1, F[i - 3] + 2)
    Lý do là:
    - Khi chọn chai i và chai i-2 thì ko thể chọn chai i-1.
    - Khi chọn chai i và chai i-3 thì phải chọn chai i-1.
    - Mình ko dùng F[i-1] vì mình ko chắc có chọn chai i-1 hay không. Với lại, khi chọn chai i-3 thì đã chọn luôn chai i-1 rồi.
    Giá trị ban đầu cho mảng F là:
    Mã:
    F[1] = 1, F[2] = 2; F[3] = 2;
    Kết quả sẽ nằm ở F[n]. Nếu bạn muốn in ra thì truy xuất ngược từ phần tử F[n], xem thử nó lấy max từ phần tử i-3 hay i-2. Lưu ý khi in i-3 thì phải in luôn i-1 nhé.
    Bạn cũng có thể tốn thêm 1 mảng để lưu trữ dấu. Ví dụ như track[i] sẽ lưu i-2 hoặc là i-3 tùy theo hàm max. Bạn lưu ý khi khởi tạo mảng dấu nhé.

    Cách ko cần QHĐ: mình sẽ lấy 2 chai liên tiếp, bỏ 1 chai; rồi lấy 2 chai liên tiếp, bỏ 1 chai,... Như vậy, công thức tính số lượng chai rượu tối đa là:
    Mã:
    n div 3 * 2 + n  mod 3
    Còn nếu mình muốn in ra thì chỉ cần check
    Mã:
    if i mod 3 <> 0
    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. 3 thành viên đã cảm ơn tengiday:


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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi tengiday Xem bài viết
    Thật ra bài này ko cần tới QHĐ, nhưng nếu muốn thì bạn có thể thử cách sau:
    F[i] = số lượng chai rượu tối đa Bờm uống đc nếu uống chai thứ i.
    Như vậy,
    Mã:
    F[i] = max (F[i - 2] + 1, F[i - 3] + 2)
    Lý do là:
    - Khi chọn chai i và chai i-2 thì ko thể chọn chai i-1.
    - Khi chọn chai i và chai i-3 thì phải chọn chai i-1.
    - Mình ko dùng F[i-1] vì mình ko chắc có chọn chai i-1 hay không. Với lại, khi chọn chai i-3 thì đã chọn luôn chai i-1 rồi.
    Giá trị ban đầu cho mảng F là:
    Mã:
    F[1] = 1, F[2] = 2; F[3] = 2;
    Kết quả sẽ nằm ở F[n]. Nếu bạn muốn in ra thì truy xuất ngược từ phần tử F[n], xem thử nó lấy max từ phần tử i-3 hay i-2. Lưu ý khi in i-3 thì phải in luôn i-1 nhé.
    Bạn cũng có thể tốn thêm 1 mảng để lưu trữ dấu. Ví dụ như track[i] sẽ lưu i-2 hoặc là i-3 tùy theo hàm max. Bạn lưu ý khi khởi tạo mảng dấu nhé.

    Cách ko cần QHĐ: mình sẽ lấy 2 chai liên tiếp, bỏ 1 chai; rồi lấy 2 chai liên tiếp, bỏ 1 chai,... Như vậy, công thức tính số lượng chai rượu tối đa là:
    Mã:
    n div 3 * 2 + n  mod 3
    Còn nếu mình muốn in ra thì chỉ cần check
    Mã:
    if i mod 3 <> 0
    À mình quên nói là số rượu tính bằng dung tích
    Ví dụ
    Input:
    6
    6 10 10 13 10 10

    thì Output là: 10 10 10 10

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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi Richard Annowit Xem bài viết
    À mình quên nói là số rượu tính bằng dung tích
    Ví dụ
    Input:
    6
    6 10 10 13 10 10

    thì Output là: 10 10 10 10
    Như vậy thì giải bài này hơi khác tí xíu nhé.
    F[i] = dung tích rượu lớn nhất mà Bờm uống tới chai thứ i. Lưu ý: chai thứ i có thể uống hoặc không uống.
    Mình có công thức QHĐ như sau:
    Mã:
    F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).
    Có nghĩa rằng khi uống tới chai thứ i thì dung tích max sẽ là max từ 1 trong 3 trường hợp sau:
    - Uống chai thứ i - 1, nhưng ko uống chai thứ i.
    - Uống chai thứ i - 2, ko uống chai thứ i - 1, uống chai thứ i.
    - Uống chai thứ i - 3, ko uống chai thứ i - 2, uống chai thứ i - 1, uống chai thứ i.
    Khởi tạo mảng F:
    Mã:
    F[1] = a[1], F[2] = a[1] + a[2], F[3] = max(a[1] + a[2], a[1] + a[3], a[2] + a[3]).
    Kết quả sẽ đc lưu ở F[n]. Muốn in ra Bờm đã uống chai nào thì mình phải đi ngược mảng F, xem coi F[n] đến từ max của trường hợp nào.

    Mình viết cho bạn 1 đoạn duyệt ngược mảng F chừng nào phần tử còn lớn hơn 3 nhé.
    Mã:
    t := n;
    while (t > 3) do
       begin
          if (f[t] = f[t - 1]) then
          begin
             write(a[t - 1], ' ');
             t := t - 1;
          end
          else if (f[t] = f[t - 3] + a[t - 1] + a[t]) then
             begin
                write(a[t], ' ', a[t - 1], ' ');
                t := t - 3;
             end
             else if (f[t] = f[t - 2] + a[t]) then
                begin
                    write(a[t], ' ');
                    t := t - 2;
                end;
         end;
    Sau khi ra khỏi dòng while loop, t <= 3, thì bạn phải viết 1 đoạn code riêng nữa. Mình cho bạn thêm input và output để test:

    Input:
    6
    3 2 1 4 5 6
    Output:
    6 5 2 3

    Input:
    6
    6 1 5 3 2 1
    Output:
    1 3 5 6

    (lưu ý 2 output trên ra 2 kết quả dung tích rượu khác nhau 16 vs 15, mặc dù đều là cùng 6 số).

    Những trường hợp đặc biệt như n = 1, 2, 3 thì bạn nhớ xử lý nhé.

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


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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi tengiday Xem bài viết
    Như vậy thì giải bài này hơi khác tí xíu nhé.
    F[i] = dung tích rượu lớn nhất mà Bờm uống tới chai thứ i. Lưu ý: chai thứ i có thể uống hoặc không uống.
    Mình có công thức QHĐ như sau:
    Mã:
    F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).
    Có nghĩa rằng khi uống tới chai thứ i thì dung tích max sẽ là max từ 1 trong 3 trường hợp sau:
    - Uống chai thứ i - 1, nhưng ko uống chai thứ i.
    - Uống chai thứ i - 2, ko uống chai thứ i - 1, uống chai thứ i.
    - Uống chai thứ i - 3, ko uống chai thứ i - 2, uống chai thứ i - 1, uống chai thứ i.
    Khởi tạo mảng F:
    Mã:
    F[1] = a[1], F[2] = a[1] + a[2], F[3] = max(a[1] + a[2], a[1] + a[3], a[2] + a[3]).
    Kết quả sẽ đc lưu ở F[n]. Muốn in ra Bờm đã uống chai nào thì mình phải đi ngược mảng F, xem coi F[n] đến từ max của trường hợp nào.

    Mình viết cho bạn 1 đoạn duyệt ngược mảng F chừng nào phần tử còn lớn hơn 3 nhé.
    Mã:
    t := n - 1;
    while (t > 3) do
       begin
          if (f[t] = f[t - 1]) then
          begin
             write(a[t - 1], ' ');
             t := t - 1;
          end
          else if (f[t] = f[t - 3] + a[t - 1] + a[t]) then
             begin
                write(a[t], ' ', a[t - 1], ' ');
                t := t - 3;
             end
             else if (f[t] = f[t - 2] + a[t]) then
                begin
                    write(a[t], ' ');
                    t := t - 2;
                end;
         end;
    Sau khi ra khỏi dòng while loop, t <= 3, thì bạn phải viết 1 đoạn code riêng nữa. Mình cho bạn thêm input và output để test:

    Input:
    6
    3 2 1 4 5 6
    Output:
    6 5 2 3

    Input:
    6
    6 1 5 3 2 1
    Output:
    1 3 5 6

    (lưu ý 2 output trên ra 2 kết quả dung tích rượu khác nhau 16 vs 15, mặc dù đều là cùng 6 số).

    Những trường hợp đặc biệt như n = 1, 2, 3 thì bạn nhớ xử lý nhé.
    Mình làm được rồi, cảm ơn bạn nha!!! Bạn nhiệt tình giúp đỡ thật.
    Nhưng mà bạn ơi
    Mã:
     F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).
    Mình bỏ qua F[i-1] mà mình làm thế này có được không?
    Mã:
    f[i]:=max(f[i-3]+a[i-1]+a[i],f[i-2]+a[i])
    Còn cái truy vết tìm nghiệm của bạn s mình copy vào chạy thì không đúng.

  8. Đã cảm ơn Richard Annowit:


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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    1) Bạn cho mình biết gọi (định nghĩa) mảng f là gì và khởi tạo giá trị như thế nào và kết quả được đọc từ đâu để mình xem. Bạn thử test này xem nhé:
    Input:
    6
    3 2 1 4 15 2
    Output:
    15 4 2 3

    Tổng max phải là 24. Mình nghĩ bạn nên build mảng F trước, chắc chắn nó đúng rồi hãy nghĩ tới duyệt ngược sau.

    2) Mình có sửa lại là t := n. Tại mình chuyển từ C++ sang Pascal cho nên phải đổi index của mảng.

  10. Đã cảm ơn tengiday:


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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi tengiday Xem bài viết
    1) Bạn cho mình biết gọi (định nghĩa) mảng f là gì và khởi tạo giá trị như thế nào và kết quả được đọc từ đâu để mình xem. Bạn thử test này xem nhé:
    Input:
    6
    3 2 1 4 15 2
    Output:
    15 4 2 3

    Tổng max phải là 24. Mình nghĩ bạn nên build mảng F trước, chắc chắn nó đúng rồi hãy nghĩ tới duyệt ngược sau.

    2) Mình có sửa lại là t := n. Tại mình chuyển từ C++ sang Pascal cho nên phải đổi index của mảng.
    Tổng max mình thử hết các input rồi đúng hết rồi. Lúc làm mình cũng xem mảng F coi có sai sót j ko rồi thấy đúng rồi...Nhưng truy vết lại bằng cách trên vẫn cho ra nghiệm sai mặc dù mình sửa lại là t:=n rồi

  12. #8
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 297085
    Bài gửi
    780

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    tengiday bá đạo quá, cái gì cũng biết à
    I have nothing...

  13. 3 thành viên đã cảm ơn Ihavenothing:


  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: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi Richard Annowit Xem bài viết
    Tổng max mình thử hết các input rồi đúng hết rồi. Lúc làm mình cũng xem mảng F coi có sai sót j ko rồi thấy đúng rồi...Nhưng truy vết lại bằng cách trên vẫn cho ra nghiệm sai mặc dù mình sửa lại là t:=n rồi
    Bạn bỏ dòng " write(a[t - 1], ' ') " trong phần if đầu tiên " if (a[t] = a[t - 1]) " xem thử. Mình viết vội nên ko test hết.
    Bạn cho mình xem nguyên code nhé, như vậy sẽ dễ biết hơn.

  15. Đã cảm ơn tengiday:


  16. #10
    Ðến Từ
    Hà Nội
    Thành Viên Thứ: 280098
    Giới tính: Nam
    Bài gửi
    2.046

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi Ihavenothing Xem bài viết
    tengiday bá đạo quá, cái gì cũng biết à
    Anh ý đang học cao học cao học ở United States đó đừng có đùa
    Nhận tư vấn các vấn đề về Tình Yêu

  17. 2 thành viên đã cảm ơn Joinal457:


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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Trích Nguyên văn bởi tengiday Xem bài viết
    Bạn bỏ dòng " write(a[t - 1], ' ') " trong phần if đầu tiên " if (a[t] = a[t - 1]) " xem thử. Mình viết vội nên ko test hết.
    Bạn cho mình xem nguyên code nhé, như vậy sẽ dễ biết hơn.
    Xin lỗi a hổm rài bận quá. Code e đây có gì a sửa giúp e nha!!!
    Mã:
    const fi='d:\pascal\qhd\bottles\input.txt';var i,n:longint; f,a:array[0..100] of longint;
    procedure input;
    var f:text;
    begin
        assign(f,fi);
        reset(f);
        readln(f,n);
        for i:=1 to n do read(f,a[i]);
        close(f);
    end;
    function max(a,b:longint):longint;
    begin
        if a>b then exit(a) else exit(b);
    end;
    procedure qhd;
    begin
        f[1]:=a[1]; f[2]:=a[1]+a[2];
        f[3]:=max(max(a[1]+a[2],a[2]+a[3]),a[1]+a[3]);
        for i:=4 to n do
            f[i]:=max(f[i-2]+a[i],f[i-3]+a[i-1]+a[i]);
    end;
    procedure rslt;
    var t:longint;
    begin
        t := n;
    while (t > 3) do
       begin
          if (f[t] = f[t - 1]) then
          begin
             t := t - 1;
          end
          else if (f[t] = f[t - 3] + a[t - 1] + a[t]) then
             begin
                write(a[t], ' ', a[t - 1], ' ');
                t := t - 3;
             end
             else if (f[t] = f[t - 2] + a[t]) then
                begin
                    write(a[t], ' ');
                    t := t - 2;
                end;
            end;
    end;
    begin
        input;
        qhd;
        rslt;
        readln; end.

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

    Reply: Giải giúp mình bài này bằng Quy Hoạch Động với

    Đoạn codes này của bạn cần thêm vào tí xíu nữa mới hoàn thành được.
    1) Trong procedure qhd, cần phải lấy thêm max của F[i - 1] luôn. Lý do là theo cách mình đặt hàm F, thì F[i] là dung tích max khi uống tới chai thứ i, nhưng ko biết đc là có uống chai thứ i hay không uống chai thứ i. Để thấy điều này, bạn lấy test ở post #6 của mình là thấy:
    Output đúng là 15 4 2 3 (F[6] = 24).
    Nếu ko lấy max của F[i - 1] thì output sẽ ra là 2 15 2 3 (F[6] = 22).

    2) Sau khi ra khỏi dòng while loop rồi, bạn cần xử lý trường hợp t = 1, 2, 3. Cách làm cũng tương tự như trong vòng loop; bạn có thể nhìn vào cách khởi tạo của mảng F để xem thử giá trị của nó đến từ phần tử nào nhé.

    Good luck.

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


Trang 1/2 12 cuối