Giới Thiệu Về Thuật Toán Tham Lam - Greedy Algorithm(Phần 2)

• Tin Tức Tin tức An ninh mạng Bản tin WhiteHat
• Thành viên
• Có gì mới
• Video
• Wargame
• Vinh Danh

Đăng nhập

Tìm kiếm

Toàn bộ Chủ đề Diễn đàn này This thread Chỉ tìm trong tiêu đề Bởi: Tìm Tìm nâng cao…

• Hoạt động gần đây
• Đăng ký

Đăng nhập Đăng ký Giới thiệu Liên hệ

CỘNG ĐỒNG AN NINH MẠNG VIỆT NAM

@ 2009 - 2021 Bkav Corporation

Install the app Install

• Thảo luận
• ACM/Programming

You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser. Giới thiệu về thuật toán tham lam - Greedy Algorithm (Phần 2)

• Bắt đầu vothuaphucnguyen
• Ngày bắt đầu 07/11/2016

Chia sẻ: Facebook Twitter Reddit Pinterest Tumblr WhatsApp Email Chia sẻ Liên kết V

vothuaphucnguyen

White---

31/08/2016 8 6 bài viết Giới thiệu về thuật toán tham lam - Greedy Algorithm (Phần 2) 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 Comment

tstarnpro;n60468 đã viết: 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 Nhấn để mở rộng...

Cám ơn góp ý của bạn. Comment 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é! Comment Bạn phải đăng nhập hoặc đăng ký để phản hồi tại đây. Bài viết liên quan

Ronaldo Béo trong giới thuật toán !

• Ngày bắt đầu 03/06/2020
• 0

Học lập trình phát triển ứng dụng trên mạng ngang hàng. Tut1 - Giới thiệu và cài môi trường

• Ngày bắt đầu 16/11/2019
• 0

[Giới thiệu sản phẩm] GSniffer - Xin dừng chân để góp ý

• Ngày bắt đầu 18/08/2017
• 1

Cơ bản về cấu trúc dữ liệu và giải thuật – Phần hai: Giới thiệu cấu trúc dữ liệu

• Ngày bắt đầu 14/02/2017
• 0

Giới thiệu về thuật toán chia để trị

• Ngày bắt đầu 07/11/2016
• 0

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

• Ngày bắt đầu 06/10/2016
• 2

Bên trên