Bài Toán Cái Túi - Quy Hoạch Động

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

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:

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)

Bảng phương án:

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: 86583 Số lượt thích: 9 người (đàm thị lang, Hoàng Thị Châm, Nguyễn Kim Thanh, ...)