Trang 1 của 2 12 CuốiCuối
Kết quả 1 đến 10 của 13
  1. #1
    Ngày tham gia
    Aug 2015
    Bài viết
    0

    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.

  2. #2
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    Trích dẫn Gửi bởi tengiday
    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

  3. #3
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    tengiday bá đạo quá, cái gì cũng biết à [IMG]images/smilies/troll2/xucdong2.gif[/IMG]

  4. #4
    Ngày tham gia
    Dec 2015
    Bài viết
    0
    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

  5. #5
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    [QUOTE="tengiday"]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ã:
    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
    </div>

    </div>
    </div>
    </div>À 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

  6. #6
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi Richard Annowit
    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.

  7. #7
    Ngày tham gia
    Aug 2015
    Bài viết
    1
    Trích dẫn Gửi bởi Ihavenothing
    tengiday bá đạo quá, cái gì cũng biết à [IMG]images/smilies/troll2/xucdong2.gif[/IMG]
    [IMG]images/smilies/funny/beat_brick.gif[/IMG] Anh ý đang học cao học cao học ở United States đó đừng có đùa

  8. #8
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    Trích dẫn Gửi bởi Richard Annowit
    À 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é.

  9. #9
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    [QUOTE="tengiday"]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ã:
    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é.</div>

    </div>
    </div>
    </div>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.

  10. #10
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    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.

 

 
Trang 1 của 2 12 CuốiCuối

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
Múi giờ GMT +7. Bây giờ là 03:26 PM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2024 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.