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 ...
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 gi và giá trị vi. 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 <= n-1, Bước 3, ngược lại Bước 9
Bước 3: Đặt j=0.
Bước 4: Nếu j <= n, Bước 5, ngược lại Bước 8
Bước 5: Nếu t[i].Dongia<t[j].Dongia, Bước 6, ngược lại Bước 7
Bước 6: Đặt i = bientam.
i=j.
j=bientam.
Bước 7: Đặt j=j+1, quay lại Bước 4.
Bước 8: Đặt i=i+1,quay lại Bước 2.
Bước 9: Kết thúc.
Sơ đồ khối.
Hàm Thuật toán.
Bước 1: Đặt i = 0, S=W
Bước 2: Nếu i < n, Bước 3,ngược lại Bước 8
Bước 3: Đặt t[i].Phuongan = S / t[i].Trongluong.
Bước 4: Đặt S = S - (t[i].Phuongan * t[i].Trongluong).
Bước 5: Kết xuất “Phuongan”
Bước 6: Đặt i = i + 1, quay lại Bước 3.
Bước 7: Kết xuất “ Trong luong con du cua balo”
Bước 7: Kết thúc.
Sơ đồ khối
Đây là 2 hàm chính mình sử dụng trong đoạn code. Code mình viết bằng C++
Note :
Xin lỗi về sự chậm trễ
Nếu ai cần code có thể comment mail bên dưới mình sẽ gửi. Vì do đoạn code khá dài và có vài kí tự không viết được trên trang này nên mình không thể đăng đoạn code được . Thanks
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 gi và giá trị vi. 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 <= n-1, Bước 3, ngược lại Bước 9
Bước 3: Đặt j=0.
Bước 4: Nếu j <= n, Bước 5, ngược lại Bước 8
Bước 5: Nếu t[i].Dongia<t[j].Dongia, Bước 6, ngược lại Bước 7
Bước 6: Đặt i = bientam.
i=j.
j=bientam.
Bước 7: Đặt j=j+1, quay lại Bước 4.
Bước 8: Đặt i=i+1,quay lại Bước 2.
Bước 9: Kết thúc.
Sơ đồ khối.
Hàm Thuật toán.
Bước 1: Đặt i = 0, S=W
Bước 2: Nếu i < n, Bước 3,ngược lại Bước 8
Bước 3: Đặt t[i].Phuongan = S / t[i].Trongluong.
Bước 4: Đặt S = S - (t[i].Phuongan * t[i].Trongluong).
Bước 5: Kết xuất “Phuongan”
Bước 6: Đặt i = i + 1, quay lại Bước 3.
Bước 7: Kết xuất “ Trong luong con du cua balo”
Bước 7: Kết thúc.
Sơ đồ khối
Đây là 2 hàm chính mình sử dụng trong đoạn code. Code mình viết bằng C++
Note :
Xin lỗi về sự chậm trễ
Nếu ai cần code có thể comment mail bên dưới mình sẽ gửi. Vì do đoạn code khá dài và có vài kí tự không viết được trên trang này nên mình không thể đăng đoạn code được . Thanks
COMMENTS