Giới thiệu về thuật toán tham lam - Greedy Algorithm (Phần 2)

[vothuaphucnguyen]

Ví dụ về thuật toán tham lam_ BÀI TOÁN BALO

Yêu cầu

Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, đồ vật thứ i có trọng lượng g[SUB]i[/SUB] và giá trị v[SUB]i[/SUB]. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô (chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu) sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất.

​

Theo yêu cầu của bài toán thì ta cần những đồ vật có giá trị cao mà trọng lượng lại nhỏ để sao cho có thể mang được nhiều “đồ quý”, sẽ là hợp lý khi ta quan tâm đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượng. Đơn giá càng cao thì đồ càng quý.

Từ đó ta có kỹ thuật Tham lam áp dụng cho bài toán này là:
1. Tính đơn giá cho các loại đồ vật.
2. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ.
3. Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép.
4. Xác định trọng lượng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa.

Ví dụ

Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng (hình 1)

Từ bảng đã cho ta tính đơn giá cho các loại đồ vật và sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng (hình 2).

Theo đó thì thứ tự ưu tiên để chọn đồ vật là B, A, D và cuối cùng là C.

Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vât loại B, trọng lượng còn lại trong ba lô là 37 - 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C.Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và một cái loại C. Tổng trọng lượng là 3*10 + 1*4 + 1*2 = 36 và tổng giá trị là 3*25+1*6+1*2 = 83.

Thuật toán

Hàm sắp xếp.
Bước 1: Đặt i=0.
Bước 2: Nếu i

 

Tham lam giải quyết nhanh chóng và cũng có thể tối ưu trong một số trường hợp nhưng với những trường hợp đặc biệt thì không còn đúng nữa.
Ví du:
S=10

Đồ vật	Trọng lượng	Giá trị	Đơn giá
A	7	9	9/7
B	6	6	1
C	4	4	1

Tham lam sẽ chọn đồ vật A, nhưng tối ưu là B và C

 

Tham lam giải quyết nhanh chóng và cũng có thể tối ưu trong một số trường hợp nhưng với những trường hợp đặc biệt thì không còn đúng nữa.
Ví du:
S=10

Đồ vật	Trọng lượng	Giá trị	Đơn giá
A	7	9	9/7
B	6	6	1
C	4	4	1

Tham lam sẽ chọn đồ vật A, nhưng tối ưu là B và C

Cám ơn góp ý của bạn.

 

Chào Add, Add ơi cho em xin thuật toán bài ba lô này với ạ, em cám ơn nhiều nhé!