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

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 = 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 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

Nhấn để mở rộng...

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ấn để mở rộng...

F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).

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]).

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;

tengiday:

Như vậy thì giải bài này hơi khác tí xíu nhé.
F = 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é.

Nhấn để mở rộng...

 [COLOR=#000000]F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).[/COLOR]

[FONT=Consolas]f[i]:=[/FONT][FONT=Consolas]max[/FONT][FONT=Consolas](f[i-[/FONT][FONT=Consolas]3[/FONT][FONT=Consolas]]+a[i-[/FONT][FONT=Consolas]1[/FONT][FONT=Consolas]]+a[i],f[i-[/FONT][FONT=Consolas]2[/FONT][FONT=Consolas]]+a[i])[/FONT]

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.

Nhấn để mở rộng...

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

Nhấn để mở rộng...

Ihavenothing:

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

Nhấn để mở rộng...

tengiday:

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.

Nhấn để mở rộng...

[FONT=Consolas]const[/FONT][FONT=Consolas] fi=[/FONT][FONT=Consolas]'d:\pascal\[/FONT][FONT=Consolas]qhd[/FONT][FONT=Consolas]\bottles\[/FONT][FONT=Consolas]input[/FONT][FONT=Consolas].txt'[/FONT][FONT=Consolas];[/FONT][FONT=Consolas]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; [/FONT][FONT=Consolas]end[/FONT][FONT=Consolas].[/FONT]

tengiday:

Đ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 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.

Nhấn để mở rộng...