Gốc > Một số bài toán Quy Hoạch Động >

Bài toán cái túi

BÀI 1: LỚP BÀI TOÁN CÁI TÚI

I. TỔNG QUAN

1. Mô hình

Trong siêu thị có n đồ vật (n≤1000), đồ vật thứ i có trọng lượng là W[i]≤10­00 và giá trị V[i] ≤1000. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M (M≤1000). Hỏi tên trộm sẽ lấy đi những đồ vật nào để được tổng giá trị lớn nhất.

Giải quyết bài toán trong các trường hợp sau:

  • Mỗi vật chỉ được chọn một lần.
  • Mỗi vật được chọn nhiều lần (không hạn chế số lần)

InputData: file văn bản Bag.inp

  • Dòng 1: n, M cách nhau ít nhất một dấu cách
  • n dòng tiếp theo: Mỗi dòng gồm 2 số Wi, Vi, là chi phí và giá trị đồ vật thứ i.

OutputData: file văn bản bag.out: Ghi giá trị lớn nhất tên trộm có thể lấy

Example

caitui_400

2. Hướng dẫn giải

Trường hợp mỗi vật được chọn 1 lần

Ta nhận thấy rằng: Giá trị của cái túi phụ thuộc vào 2 yếu tố: Có bao nhiêu vật đang được xét và trọng lượng còn lại cái túi có thể chứa được, do vậy chúng ta có 2 đại lượng biến thiên. Cho nên hàm mục tiêu sẽ phụ thuộc vào hai đại lượng biến thiên. Do vậy bảng phương án của chúng ta sẽ là bảng 2 chiều.

Gọi F[i,j] là tổng giá trị lớn nhất của cái túi khi xét từ vật 1 đến vật i và trọng của cái túi chưa vượt quá j. Với giới hạn j, việc chọn tối ưu trong số các vật {1,2,…,i-1,i} để có giá trị lớn nhất sẽ có hai khả năng:

Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật {1,2,…,i-1} với giới hạn trọng lượng là j, tức là:

F[i,j]:=F[i-1,j].

Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật {1,2,…,i-1} với giới hạn trọng lượng j-W[i] tức là về mặt giá trị thu được:

F[i,j]:=V[i]+F[i-1,j-W[i]]

Vậy chúng ta phải xem xét xem nếu chọn vật i hay không chọn vật i thì sẽ tốt hơn. Từ đó chúng ta có công thức truy hồi như sau.

  • F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất.
  • F[i,j]= max(F[i-1,j], V[i]+F[i-1,j-W[i]]

Trường hợp mỗi vật được chọn nhiều lần: Tương tự như suy luận ở trên ta xét:

Nếu không chọn vật thứ i thì F[i,j] là giá trị lớn nhất có thể chọn trong số các vật {1,2,…,i-1} với giới hạn trọng lượng là j, tức là:

F[i,j]:=F[i-1,j].

Nếu có chọn vật thứ i (phải thỏa điều kiện W[i] ≤ j) thì F[i,j] bằng giá trị vật thứ i là V[i] cộng với giá trị lớn nhất có thể có được bằng cách chọn trong số các vật {1,2,…,i} (vì vật i vẫn có thể được chọn tiếp) với giới hạn trọng lượng j-W[i] tức là về mặt giá trị thu được:

F[i,j]:=V[i]+F[i,j-W[i]]

Do vậy chúng ta có công thức truy hồi như sau:

  • F[0,j] = 0 (hiển nhiên) – Bài toán con nhỏ nhất.
  • F[i,j]= max(F[i-1,j], V[i]+F[i,j-W[i]]

3. Bảng phương án

Ta xây dựng bảng phương án dựa trên công thức truy hồi trên. Để kiểm tra kết quả có chính xác hay không (nếu không chính xác chúng ta xây dựng lại hàm mục tiêu). Thông qua cách xây dựng hàm mục tiêu và bảng phương án chúng ta sẽ định hướng việc truy vết.

Example (trường hợp mỗi vật chỉ được chọn 1 lần)

Bảng phương án:

pa1_400

Vậy chúng ta có thể chọn vật 2, 3, 4, 5.

Example (trường hợp mỗi vật được chọn nhiều lần)

in1_400

Bảng phương án:

pa2_400

Chúng ta có thể chọn vật 4 (3 lần) và vật 5 (3 lần).

4. Truy vết

Trường hợp 1: Trong bảng phương án F[n,m] chính là giá trị lớn nhất thu được khi chọn trong cả n vật với giới hạn trọng lượng là M.

Nếu f[n,M]=f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu f[n,M]≠f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về f[n-1,M-Wn].

Trường hợp 2: Trong bảng phương án F[n,m] chính là giá trị lớn nhất thu được khi chọn trong cả n vật với giới hạn trọng lượng là M.

Nếu f[n,M]=f[n-1,M] thì tức là không chọn vật thứ n, ta truy về f[n-1,M]. Còn nếu f[n,M]≠f[n-1,M] thì ta thông báo rằng phép chọn tối ưu có chọn vật thứ n và truy về f[n,M-Wn].

5. Cài đặt

Program Bag;

Const

            limit = 1000;

Var

            V,W: Array[1..limit] of integer;

            F: Array[0..limit,0..limit] of integer;

            n,M,i,j: integer;

            fi,fo: text;

{---------------------------------------------------------------------------}

Procedure inputdata;

            Begin

                        assign(fi,'bag.inp');

                        reset(fi);

                        readln(fi,n,m);

                        for i:=1 to n do readln(fi,w[i],v[i]);

                        close(fi);

            End;

{---------------------------------------------------------------------------}

Procedure outputdata;

            Begin

                        assign(fo,'bag.out');

                        rewrite(fo);

                        write(fo,F[n,m]);

                        close(fo);

            End;

{---------------------------------------------------------------------------}

Function max(a,b:integer):integer;

            Begin

                        if a>b then max:=a

                        else max:=b;

            End;

{---------------------------------------------------------------------------}

Procedure process;

            Begin

                        for i:=1 to n do

                                    for j:=1 to m do

                                                if w[i]<=j then

                                                            F[i,j]:=max(F[i-1,j],F[i-1,j-w[i]]+v[i])

                                                else      F[i,j]:=F[i-1,j];

            End;

{---------------------------------------------------------------------------}

Begin

            inputdata;

            process;

            outputdata;

End.


Nhắn tin cho tác giả
Nguyễn Nho @ 18:31 03/07/2012
Số lượt xem: 49547
Số lượt thích: 7 người (Nguyễn Kim Thanh, Nguyễn Quang Minh, Huong Huong, ...)
No_avatar

cách hướng dẫn của thầy rất dễ hiểu, thầy có thể share cho em cuốn sách này được không? mail của em dddan1978xt@gmail.com. xem cám ơn và hậu tạ.

No_avatar

tài liệu thầy rất hay. Không biết thầy có thể share tài liệu ko?

 

No_avatar

truy như cái cl, chia hai trường hợp giống nhau cả hai :V, code ko có truy vết trên hd truy vết, bài xàm l

No_avatar

Hy Àdt Ádf  đề bài có yêu cầu truy vết đâu làm gì gắt v bạn

No_avatarf

thầy share tài liệu cho em được không ạ. mail em là: lethienquan28052006@gmail.com

Avatar

Cảm ơn thầy

No_avatar

Em muốn có tài liệu để học tập, mong thầy chỉ em cách có được tài liệu! Cảm ơn thầy!

Mong thầy hồi âm: melathienthan@gmail.com

 
Gửi ý kiến